我有一个嵌套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，这就是我迷路的地方。指针吗?
您几乎总是可以插入常识告诉您包含最坏情况的数字。除非所述的最坏情况保证只运行固定数量的时间而不考虑N(即所有循环都是接近最优的，除了最多5个循环不是，即使我们循环1000次-非常罕见)-然后只做最坏情况的数学。
这适用于每个单独的循环:取每个循环的最坏情况。这是正确的，除非在循环之间存在链接，例如，如果内部循环运行'最坏情况'，只有在某些外部循环保证运行最佳情况时，反之亦然-当存在明确的关系时。
那么，我们把它应用到这里:
- 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的增长，它会很快下降)。
如果你不确定数学是否正确，试着找出线性。这就保证了。在这种情况下，最好的情况是当i为0时，在这种情况下j循环只运行一次，而最坏的情况是j循环运行n*n次。至关重要的是，j循环的特征是线性的:只要绘制出在i循环的"生命周期"中j循环的性能会发生什么变化，这是一个简单的直接关系。前5个j循环运行一次，后5个j循环运行两次，一直到最后一个j循环运行n*n/5次。
所有j循环的"平均值"是这一行的中间:n*n/5的一半。也就是n*n/10，常数不重要，所以还是n*n。这就是为什么这是O(n^4)，就像for (j = 0; j < n*n; j++)一样。