watermelon8338   4년 전

겹치지 않는 난수 생성할 때

대부분 글들 보면 i번째 난수 생성하고 0~ i-1 까지 겹치는지 확인하고 겹치면 다시 난수 생성

이런식이던데 너무 난수 개수를 크게 잡으면 시간이 너무 오래 걸려서 질문해봅니다

더 좋은 방식있으면 방향만이라도 잡아주시면 감사하겠습니다.

그리고 위의 방식은 시간복잡도로 표현하면 평균적으로 O(n^2) 같은데 맞나요??

qvixnh22   4년 전

i번째 난수를 생성한 이후 0~i-1번째와 값이 같은 지 비교할 때 다양한 방법을 시도할 수 있습니다.

난수의 범위가 작은 경우 불린 배열을 만들어 해당 값이 난수로 생성된 경우 불린 값을 바꿔 상수시간만에 확인하는 방법도 있을거고, 일단 전체 n개의 난수를 만든 뒤 정렬한 후 중복되는 값들을 재지정하는 방식도 가능해 보입니다.

이전에 나왔던 모든 난수를 비교하는 시간은 O(n^2), 확인하는 배열을 만든 경우는 O(n)이 소요됩니다.

정렬후 이진탐색을 이용해 중복 여부를 확인한다면 여러가지 방식이 가능할텐데 가장 간단하게 재설정때마다 전체 배열을 정렬한다고 가정하고 난수 생성이므로 모두 같은 수가 나오는 최악의 경우 등을 배제하여 항상 재설정한 난수의 절반은 중복되지 않는다고 가정하면 O(nlogn)의 시간이 소요될 것입니다.

watermelon8338   4년 전

정렬 알고리즘을 공부 중이랑 테스트용으로 난수의 범위가 크고 정렬이 안된 배열이 필요합니다

int arr[100000];
for (int i = 0; i < 100000; i++)
{
    arr[i] = rand()%30000 + rand() % 30001 + rand() % 30001 + rand() % 30001 + 1;
    for (int j = 0; j < i; j++)
        if (arr[i] == arr[j])
            i--;
}

이럴 경우 0이나 나올 수 있는 끝의 수가 상대적으로 나올 확률이 적어보여서 좋지않은 코드같은데

좋은 생각있으면 공유 부탁드립니다..

qvixnh22   4년 전

C의 rand()함수는 0에서 32767 사이의 정수를 반환합니다. 주어진 코드에서 난수 생성부는 각 항에서 0에서 2767까지가 두 번, 나머지가 한 번씩 나옵니다. 더 중요한 것은 이런 항을 여러 번 더했기 때문에 큰 수의 법칙에 의해 평균에 가까운 수가 나올 확률이 더 높습니다.

이를 해결하기 위해서는 rand()함수를 한 번만 사용하는 것이 좋습니다. 만약 32767보다 큰 난수가 필요한 경우라면 rand()*32767+rand()와 같이 큰 수의 법칙을 따르지 않는 중첩을 사용할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.