algorithm - 给定代码的渐近分析

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)，内循环会在r次迭代后到达n。通过取对数，我们得到 log n = 2^r。通过再次取对数，我们有 log log n = r。您可能知道，在处理渐近行为时，对数的底数并不重要，只要它是常数即可。

因此，我们有一个循环的 n 次迭代，它本身进行 log log n 次迭代，使得整体复杂度 O (n log log n).