Генерация m различных случайных чисел в диапазоне [0..n-1]

Question

У меня есть два метода генерации m различных случайных чисел в диапазоне [0..n-1]

Метод 1:

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

Метод 2:

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

Первый метод более эффективен, когда n намного больше, чем m, тогда как второй более эффективен в противном случае. Но «намного больше», не правда ли, строгое понятие? :)

Вопрос: Какую формулу n и m следует использовать, чтобы определить, будет ли метод1 или метод2 более эффективным? (с точки зрения математического ожидания времени работы)

Answer 1

Вполне возможно, было бы проще запустить его в режиме отладки (и оставить один метод в качестве примечания) пару раз, чтобы получить среднее значение, а затем использовать другой метод, чтобы получить среднее из этого