Что такое Big-O кода, который использует генераторы случайных чисел?

Question

Я хочу заполнить массив 'a' случайными значениями от 1 до N (без повторных значений). Предположим, что Big-O of randInt (i, j) - O (1), и эта функция генерирует случайные значения от i до j.
Примеры выходных сигналов:

{1,2,3,4,5} или {2,3,1,4,5} или {5,4,2,1,3}, но не { 1,2,1,3,4}

#include<set> 
using std::set; 

set<int> S;// space O(N) ? 
int a[N]; // space O(N) 
int i = 0; // space O(1) 
do { 
    int val = randInt(1,N); //space O(1), time O(1) variable val is created many times ? 
    if (S.find(val) != S.end()) { //time O(log N)? 
     a[i] = val; // time O(1) 
     i++; // time O(1) 
     S.insert(val); // time O(log N) <-- we execute N times O(N log N) 
    } 
} while(S.size() < N); // time O(1) 

While Loop будет продолжаться, пока мы не генерировать все значения от 1 до N. Я понимаю, что набор сортирует значения в логарифмической журнале времени (N), и вставляет в log (N).

Big-O = O(1) + O(X*log N) + O(N*log N) = O(X*log N) 

Где X больше, высокая вероятность создания числа, которого нет в Set.

time O(X log N) 

space O(2N+1) => O(N), we reuse the space of val 

Где ?? очень сложно генерировать все разные числа каждый раз, когда выполняется randInt, поэтому, по крайней мере, я ожидаю выполнить N раз.
Является ли переменная X созданной много раз?
Что было бы хорошим значением для X?

Answer 1

Предположим, что RNG является идеальным. То есть, повторные вызовы randInt (1, N) генерируют i.i.d. (независимой и одинаково распределенной) последовательности значений, равномерно распределенных на {1, ..., N}.

(Конечно, в действительности ГСЧ не будет идеальным. Но давайте идти с ним, так как это делает математику проще.)

Средний случай

В первой итерации, случайная величина Вэл выбран, который, конечно, еще не входит в набор S.

В следующей итерации выбрано другое случайное значение.

• С вероятностью (N-1)/N, то это будет отличными от Вала и внутренние условным будет выполнены. В этом случае вызовите выбранное значение val .
• В противном случае (с вероятностью 1/N) выбранное значение будет равно значению . Повторите попытку.

Сколько итераций занимают в среднем до действительного (в отличие от Вала) Вала выбран? Ну, у нас есть независимая последовательность попыток, каждая из которых преуспевает с вероятностью (N-1)/N, и мы хотим знать, сколько попыток требуется в среднем до первого успеха. Это геометрическое распределение, и в общем случае геометрическое распределение с вероятностью успеха p имеет значение 1/p. Таким образом, в среднем N/(N-1) пытается выбрать значение val .

Аналогичным образом, он принимает Н/(N-2) попытки в среднем, чтобы выбрать Val отличия от Вала и Вала , и так далее. Наконец, N-е значение в среднем принимает N/1 = N попыток.

В общей сложности сделать цикл будет выполнен

раз в среднем. Сумма является N-м harmonic number, которая может быть приблизительно аппроксимирована ln (N). (Там же известный better approximation, который является немного более сложным и включает в Euler-Mascheroni constant, но п (N) является достаточно хорошим для нахождения асимптотической сложности.)

Так приближение, среднее число итераций будет N пер N.

Как насчет остальной части алгоритма? Такие вещи, как вставка N вещей в набор, также занимают не более O (N log N), поэтому можно пренебречь. Большое остающееся то, что каждая итерацию вы должны проверить, если выбранное случайное значение лежит в S, которая занимает логарифмическое время в текущем размере S. Таким образом, мы должны вычислить

, который с числового эксперименты, по-видимому, приблизительно равны N/2 * (ln N)^2 для больших N. (возможно, попросите дать доказательство этого по математике.SE). EDIT: см. this math.SE answer для краткого неофициального доказательства, и other answer to that question для более формального доказательства.

Итак, в итоге общая средняя сложность равна Θ (N (ln N)^2). Опять же, это предполагает, что RNG является идеальным.

Наихудший

Как xaxxon упоминалось, это в принципе возможно (хотя и маловероятно), что алгоритм не прекращается вообще. Таким образом, наихудшей сложностью будет O (∞).

Answer 2

Это очень плохой алгоритм для достижения вашей цели.

Просто заполните массив цифрами от 1 до N, а затем перетасуйте.

Это O (N)

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Для перемешивания, выбрать индекс от 0 до N-1 и поменять его с индексом 0. Затем выберите индекс от 1 до N-1 и поменять его с индексом 1. Весь путь до конца списка.

С точки зрения вашего конкретного вопроса, это зависит от поведения вашего генератора случайных чисел. Если он действительно случайный, он, возможно, никогда не завершится. Если это псевдослучайно, это зависит от периода генератора. Если у вас есть период в 5, у вас никогда не будет ни малейших обманов.

Answer 3

Это катастрофически плохой код со сложным поведением. Генерация первого числа - это O (1). Затем второй включает двоичный поиск, поэтому лог N и повторение генератора должны найти число. Вероятность получения нового числа равна p = 1- i/N. Таким образом, среднее число повторных запусков является взаимным и дает вам еще один коэффициент N. So O (N^2 log N).

Способ сделать это, чтобы сгенерировать числа, а затем перетасовать их. Это O (N).