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

一个提示：

第 4-10 行的运行时间不是 O(n^2)。

考虑 while 循环的 j 值：

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

这不是 O(n)。

Answer 2

对于大 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 3

使用 Sigma 表示法，您可以有条不紊地执行以下操作：