时间戳

首页 > 解决方案 > 内循环依赖外循环的嵌套 for 循环的时间复杂度

java - 内循环依赖外循环的嵌套 for 循环的时间复杂度

问题描述

我有一个嵌套的 for 循环：

for(i = 0; i < n*n; i++)
   for(j = 0; j <= i/5; j++)
      print("Hello World!");

我如何找到这个循环的时间复杂度。

我在考虑外循环，它从 0 运行到 n^2（不包括），所以它运行 n^2 + 1 次。

对于内部循环，它取决于 i ，这就是我迷路的地方。任何指针？

标签： javafor-looptime-complexitybig-o

解决方案

几乎总是你可以插入常识告诉你构成最坏情况的数字。除非所说的最坏情况保证只运行固定次数而不管 N （即所有循环都接近最优，除了最多 5 个循环不是，即使我们循环一千次 - 非常罕见） - 然后只用最坏的情况做数学。

就每个单独的循环而言，这是最坏的情况。这是正确的，除非循环之间存在链接，例如，如果内部循环运行“最坏情况”，则只有当某些外部循环保证运行最佳情况时，反之亦然 - 当存在明确的关系时。

所以，让我们在这里应用它：

  • i 从 0 运行到 n*n，这部分很容易。
  • j 从 0 到 i （我们可以忽略常数因素，因此这/5部分无关紧要，我们可以忘记它）。

j 循环的最坏情况是 i 等于n*n，这使得 j 从 0 运行到n*n。所以让我们使用它。

这实际上是正确的答案；这是一个运行n*n迭代的循环（这是j循环），并且这个过程重复n*n多次（i循环），总复杂度为O(n^4)（哎呀，随着 n 的增长，它会很快崩溃）。

如果您不确定数学是否可行，请尝试找到线性度。这保证了它。在这种情况下，最好的情况是 wheni为 0，在这种情况下 j 循环只运行一次，而最坏的情况是 j 循环运行n*n次数。至关重要的是，j循环的特征是线性的：只需画出 j 循环在 i 循环的“生命周期”内的性能发生了什么变化，这是一个简单的直线关系。前 5 j 个循环运行一次，第二个 5 j 循环运行两次，一直到运行n*n/5时间的最后一个 j 循环。

所有 j 循环的“平均值”就是该行的中间：一半n*n/5。哪个是n*n/10和常数因素无关紧要，所以仍然是n*n。因此，为什么会这样，和本来O(n^4)一样。for (j = 0; j < n*n; j++)

推荐阅读