给定代码的渐近分析

Question

我得到了以下伪代码:

 j = 1
 while j < n:
      k = 2
      while k < n:
           k = k*k
      j++

在我的想法中,这段伪代码将具有以下复杂性:

 O(n*log(n))

由于外循环执行n次.虽然内循环基本上每次将增量步长分成两半.我的想法太远了吗？

编辑:1个以上(这些不是作业,我保证,只是要了解的例子)

 for i = 1 to n:
    for j = 1 to n:
       k = j*j
       while k < n:
          k++

在这种情况下,最外面的循环将执行n次.中间回路也将执行n次,把我们现在以n ²倍.最里面的循环,正如我所说,它将执行log(n)次,将我们放在O(n ²*log(n))次.我的理解是否正确？

Answer 1

是的O (n log log n).

n就时间而言,外循环只重复内循环次数,因此它可以提供乘数n.

内环更棘手,它重复平方k.看看它是怎么回事: 2^1 -> 2^2 -> 2^4 -> 2^8 -> 2^16 -> 2^32 -> ... 所以,例如,如果n = 2^32,循环将有5迭代.在这里,log_2 (n)是32,log_2 (32)是5.

通常,如果n = 2^(2^r),内循环将在迭代n之后到达r.通过取对数,我们到达log n = 2^r.通过另一次取对数,我们得到了log log n = r.正如您可能知道的那样,对数的基数在处理渐近行为时并不重要,只要它是常数即可.

因此,我们有n一个循环的log log n迭代,它本身会进行迭代,从而产生整体复杂性O (n log log n).