-1
配列 'a'に1からNまでのランダム値（繰り返し値なし）を入力したいと思います。 randInt（i、j）のBig-OがO（1）であり、この関数がiからjまでランダムな値を生成すると仮定します。
出力の例を次に示します。乱数ジェネレータを使用するコードのBig-Oとは何ですか？
{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)
ザ・我々は1からN. にすべての値を生成するまでループを継続しますが私の理解では、設定が対数時間のログ（N）の値をソートすることで、 log（N）に挿入します。
Big-O = O(1) + O(X*log N) + O(N*log N) = O(X*log N)
ここで、Xが多いほど、セット内にない数値を生成する可能性が高くなります。
time O(X log N)
space O(2N+1) => O(N), we reuse the space of val
?? randIntが実行されるたびにすべての異なる数値を生成するのは非常に難しいので、少なくともN回実行することを期待しています。
変数Xが何度も作成されていますか？
Xにはどのような価値がありますか？
コードを書くことは、無限ループを持たないコードを書くことほど重要ではありません。 – kfsone
あなたのランダムソースについては何も知らないのです。真にランダムであれば、最悪の場合のXは∞です。 – kfsone