时间戳

首页 > 解决方案 > 给定代码的渐近分析

algorithm - 给定代码的渐近分析

问题描述

我得到了以下伪代码：

 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 2次。据我了解，最里面的循环将执行 log(n) 次，使我们处于 O(n 2 *log(n)) 次。我的理解正确吗？

标签： algorithmbig-ocomputer-scienceasymptotic-complexity

解决方案

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

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

推荐阅读