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

Question

我有一个嵌套的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，这就是我迷失的地方。有什么指示吗？

Answer 1

几乎总是你可以插入常识告诉你包含最坏情况的数字。除非所说的最坏情况保证无论N次都只运行固定的次数（即所有循环都接近最佳，除了最多5个循环不是，即使我们循环一千次——非常罕见）——那么就用最坏的情况做数学。

这适用于每个单独的循环：取每个循环的最坏情况。这是正确的，除非循环之间有联系，例如，如果内部循环运行“最坏情况”，只有当某些外部循环保证运行最佳情况时，反之亦然——当有明确的关系时。

那么，让我们在这里应用它：

• 我从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的增长，它会很快消失）。

如果你不确定数学是否正确，试着找出线性。这就保证了。在这种情况下，最好的情况是当i为0时，在这种情况下，j循环只运行一次，而最坏的情况是j循环运行n*n次。关键的是，j循环的特性是线性的：只要画出在i循环的“生命周期”内j循环的性能会发生什么，这是一个简单的直线关系。第一个5J循环运行一次，第二个5J循环运行两次，一直到最后一个j循环运行n*n/5次。

所有j循环的“平均值”仅为该行的中间值：n*n/5的一半。这是n*n/10，常数因子并不重要，所以这仍然是n*n。因此，为什么这是O（n^4），与（j=0；j）的相同