给定代码的渐近分析

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

Answer 2

是的，你是对的，第一个循环直接为 O(n)。第二部分有点棘手。我要用理性而不是严谨来展示它的 O(logn)。

所以让我们暂时假设它 k = k * 2。这是一个熟悉的序列，我们称为 O(logn)，但是我们看到任何给定循环的 k >= 2，因此我们知道序列 k = k*k 将以 O(logn) 为界，即它处于 most O(logn)。很容易看出它不是 O(1) 所以我们知道 O(1) 是下界。合起来得到O(nlogn)

Answer 3

O(n log(n))

k^log(n) 正是 k 等于或大于 n 的值。

log(n) = x means 2^x = n

你运行循环了n次。

所以复杂度是 O(n * log(n))

给定代码的渐近分析

Asymptotic analysis of a given code

algorithm

big-o

computer-science

asymptotic-complexity