i번째 난수를 생성한 이후 0~i-1번째와 값이 같은 지 비교할 때 다양한 방법을 시도할 수 있습니다.
난수의 범위가 작은 경우 불린 배열을 만들어 해당 값이 난수로 생성된 경우 불린 값을 바꿔 상수시간만에 확인하는 방법도 있을거고, 일단 전체 n개의 난수를 만든 뒤 정렬한 후 중복되는 값들을 재지정하는 방식도 가능해 보입니다.
이전에 나왔던 모든 난수를 비교하는 시간은 O(n^2), 확인하는 배열을 만든 경우는 O(n)이 소요됩니다.
정렬후 이진탐색을 이용해 중복 여부를 확인한다면 여러가지 방식이 가능할텐데 가장 간단하게 재설정때마다 전체 배열을 정렬한다고 가정하고 난수 생성이므로 모두 같은 수가 나오는 최악의 경우 등을 배제하여 항상 재설정한 난수의 절반은 중복되지 않는다고 가정하면 O(nlogn)의 시간이 소요될 것입니다.

watermelon8338 4년 전
겹치지 않는 난수 생성할 때
대부분 글들 보면 i번째 난수 생성하고 0~ i-1 까지 겹치는지 확인하고 겹치면 다시 난수 생성
이런식이던데 너무 난수 개수를 크게 잡으면 시간이 너무 오래 걸려서 질문해봅니다
더 좋은 방식있으면 방향만이라도 잡아주시면 감사하겠습니다.
그리고 위의 방식은 시간복잡도로 표현하면 평균적으로 O(n^2) 같은데 맞나요??