performance - 漸近的な予想実行時間

Question

漸近解析の質問で問題が発生しています。この問題は、関数の漸近的な最悪の場合の実行時間と漸近的な予想される実行時間の両方を要求します。Random（n）は、一様分布で1からnまでの乱数を生成します（1からnまでのすべての整数が同じように発生する可能性があります）。

Func2(A, n)
/* A is an array of integers */
1 s ← A[1];
2 k ← Random(n);
3 if (k < log2(n)) then
4    for i ← 1 to n do
5       j ← 1;
6       while (j < n) do
7          s ← s + A[i] ∗ A[j];
8          j ← 2 ∗ j;
9       end
10   end
11 end
12 return (s);

3行目（if（k <log2（n））then）が関数の予想実行時間にどのように影響するのか疑問に思いました。4行目から10行目は、最悪の場合cn ^ 2の時間で実行されると思いますが、ifステートメントが原因で、予想される実行時間をどのように導き出すかがわかりません。助けてくれてありがとう！

-マット

Answer 1

大きな n の場合、ほとんどの場合、k は log(n) よりも大きくなります。たとえば、n=1024 の場合、log(1024)=10 サイクルを実行する確率は P=log(n)/n なので、時間は

(log(n)/n)*(n*log(n))+ O(RandomFunc(n))

したがって、すべてが O(Random(n)) に依存します。O(ランダム(n)) = O(n)の場合

O(n)>O(log(n)^2) = O(n)

行 4 ～ 10 は O(nlog(n)) です

Answer 2

先端：

行 4 ～ 10 の実行時間は O(n^2) ではありません。

while ループの j の値を考えてみましょう。

j = 1、2、4、8、16、...

それは O(n) ではありません。