algorithm - O(n) 运行时算法

Question

下面的算法有运行时间O(n)根据我们教授的说法，但是我很困惑为什么不是 O(n log(n)) ，因为外循环最多可以运行 log(n)次，内部循环最多可以运行 n次。

Algoritme Loop5(n) 
i = 1 
while i ≤ n 
    j = 1 
    while j ≤ i 
       j = j + 1 
    i = i∗2

Answer 1

你的教授是对的，运行时间是O(n) .

在i - 当我们有 i=2^k 时，外层 while 循环的第 -th 次迭代对于 k=0,1,...,log n ，内部 while 循环生成 O(i)迭代。 (当我说 log n 时，我指的是以 2 为底的对数 log_2 n。)

运行时间为O(1+2+2^2+2^3+...+2^k)对于 k=floor(log n) .这总和为 O(2^{k+1})这是 O(2^{log n}) . (这来自 formula for the partial sum of geometric series 。)

因为 2^{log n} = n ，总运行时间为O(n) .

对于感兴趣的人，这里有一个证明，证明 2 的幂的总和确实等于我声称的它们的总和。 (这是更一般结果的一个非常特殊的情况。)

claim 。对于任何自然 k , 我们有 1+2+2^2+...+2^k = 2^{k+1}-1 .

证明。 注意 (2-1)*(1+2+2^2+...+2^k) = (2 - 1) + (2^2 - 2) + ... + (2^{k+1} - 2^k)所有2^i对于 0<i<k+1取消，i=0 除外和 i=k+1 , 我们剩下 2^{k+1}-1 . QED.