时间戳

首页 > 解决方案 > 如何计算嵌套循环的时间复杂度？

time-complexity - 如何计算嵌套循环的时间复杂度？

问题描述

如何计算以下算法的时间复杂度？

for(i=1;i<=n;i++)
  for(k=i;k*k<=n;k++)
   {
     Statements;
   }

据我所知，嵌套 for 循环的时间复杂度等于执行最内层循环的次数。所以这里最里面的循环是执行n*n次数，因此它是O(n^2).

是否O(n)取决于k*k<=n第二个循环中给出的条件？

谢谢！

标签： time-complexitybig-ocomplexity-theory

解决方案

算法的时间复杂度总是根据某种类型的操作来衡量的。例如，如果您Statements;有一个未知的时间复杂度，它取决于 n，那么首先描述时间复杂度会产生误导。

但是您可能想要了解的是操作方面 的时间复杂度。如果是一个恒定时间的操作，这变得特别有意义。在这种情况下，我们正在寻找的只是计算执行了多少次。如果这个数字是 3*n，那么时间复杂度就是 O(n)。Statements; Statements;Statements;

为了回答这个问题，让我们把你的嵌套循环分开。外部循环从（包括）1 到 n 迭代，所以它会运行 n 次，不管任何事情。

对于外循环的每次迭代，内循环将执行一次。它从 k=i 开始并迭代直到k*k > n, 或k > sqrt(n)。请注意，无论何时i > sqrt(n)，它都不会运行。我们可以看到，平均而言，它将运行

O(sqrt(n) + sqrt(n)-1 + sqrt(n)-2 + ... + 0) / n

迭代。通过你可以在这里找到的求和公式，这等于

O( sqrt(n) * (sqrt(n) + 1) / 2 ) = O( (n + sqrt(n))/2 ) = O( n + sqrt(n) ) = O(n).

所以是的，这种情况下的时间复杂度O(n)正如你所建议的那样。

您可以通过编写一个简单的脚本来模拟您的算法并计算Statements;. 下面在 JavaScript 中，所以它可以作为片段运行：

// Simulation
function f(n) {
  let res = 0;
  for(let i=1;i<=n;i++)
    for(let k=i;k*k<=n;k++)
      ++res;
  return res;
}

// Estimation
function g(n) {
  return ~~((n + Math.sqrt(n))/2);
}

console.log(
  f(10),
  f(100),
  f(1000),
  f(10000),
);
console.log(
  g(10),
  g(100),
  g(1000),
  g(10000),
);

我希望你觉得这很有用。

推荐阅读