以下嵌套循环的时间复杂度是多少？

for i=1 to n 
    for j=1 to i 
     for k=1 to j 
      x+=1

for i=1 to n 
    for j=1 to i 
     for k=1 to i 
      x+=1

我也觉得这一个是N 因为内部循环仍依赖于最外层循环。

请验证我的回答，并解释我为什么错了。

这是一个说明性的图n与你的算法的运行时间的各种n值（但包括一个固定的持续时间睡眠/暂停在x + = 1步，以便您可以使用n的合理值）。查看图形的形状以获得关于复杂性的最初概念。 –

或者只是绘制x的值，因为它只能增加1。但是，sum（1..n）是n *（n + 1）/ 2，它在O（n^2）复杂等级中，如n * n。因此，在外环循环计数器上线性依赖的循环边界不会改变事物。 –

在实践中，它通常要快得多，而且如果通常会发生早期失败，那么它可能非常重要。（例如，考虑在字符串中查找重复的字符，检查整个字符串以重复当前的字符，而不是检查前面的元素。对于没有重复第一个字符的巨大字符串，它是巨大的。）因为你必须分别考虑这种情况，或者说明早期采取的频率。 –

假设你有第一个正确的。那么你可以很容易认为第二个版本的复杂性至少是第一个版本的复杂性。为什么？版本之间的唯一区别是第二个版本有k = 1 to i，第一个版本有k = 1 to j。但在第一个版本中，j总是小于或等于i。所以在第二个版本中，k的循环将会经常运行得更频繁。

现在考虑这段代码：

for i=1 to n 
    for j=1 to n 
     for k=1 to n 
      x+=1

首先，表明这个时间复杂度为为O（n ）。然后，进行一个类似于我上面所做的论证，以显示此代码的复杂性大于或等于您的第二个版本的复杂性。得出这样的结论所有三个代码段的复杂性必须是为O（n 3 ）如果所述第一个的复杂度，然后显示所述第一的复杂度是为O（n 3 ）。

2015-09-24 02:27:02 Patrick87

回答