时间戳

首页 > 解决方案 > 以下代码循环的时间复杂度？

time-complexity - 以下代码循环的时间复杂度？

问题描述

我只需要有人为我解释一行代码，我不太明白。* 这只是伪代码

m: = 1, l := 0, s:= 0:
while m <= n do 
    for j = n-m to n do :
      l:= l + 1
    od 
     for j = 1 to [log n] do 
       s: = s +1 
     od 
     m := 3m 
 od

我知道第二个 for 循环是 log n 时间，while 循环是 log base 3 n 时间，但我对第一个 for 循环感到困惑？有人可以解释一下，这只是o（n）吗？j = nm 到底是做什么的？

标签： time-complexitybig-ocomplexity-theory

解决方案

第一个for循环从n-m到n。所以它有m迭代。在 while 循环的最后一次迭代中，它m基本上是n在n. 但整体复杂度要好于O(n log n)

总共有这么多迭代

(1 + log n) + (3 + log n) + (9 + log n) + ... + (n + log n)  ( log_3 n terms )
 = log_3 n * log n + (1 + 3 + 9 + ... + n)   ( n can be written as 3^(log_3 n) )
 = log_3 n * log n + (3^0 + 3^1 + 3^2 + ... + 3^(log_3 n))   (see this as a base 3 number. 11 is smaller than 100)
<= log_3 n * log n + 3^(1 + log_3 n)
 = log_3 n * log n + 3 * n

所以主导项是n，因此总体复杂性是O(n)。

推荐阅读