渐近预期运行时间(Asymptotic Expected Running Time)

渐近预期运行时间(Asymptotic Expected Running Time)

我在渐近分析问题上遇到了一些麻烦。 该问题要求渐近最坏情况运行时间和函数的渐近预期运行时间。 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））然后如何影响函数的预期运行时间。 我认为第4-10行在最坏情况下运行cn ^ 2时间，但我不确定如何根据if语句推导出预期的运行时间。 谢谢你的帮助！

-Matt

I'm having some trouble with an asymptotic analysis question. The problem asks for both the asymptotic worst case running time and the asymptotic expected running time of a function. Random(n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.)

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);

I was wondering how line 3 (if (k < log2(n)) then) effects the expected running time of the function. I believe lines 4 - 10 run at worst case cn^2 time, but I am unsure how to derive the expected running time due to the if statement. Thanks for any help!

-Matt

最满意答案

对于大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（Random（n））= O（n）

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

第4-10行是O（nlog（n））

For big n, k almost always bigger then log(n). For example for n=1024, log(1024)=10 Probability that you will execute cycle is P=log(n)/n So Time will be

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

So everything depend on O(Random(n)). If O(Random(n)) = O(n)

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

Lines 4-10 is O(nlog(n))