是嵌套for循环的时间复杂度总是O(n^2)?

Question

for (i = 1; i <= n; i++)
{
for (j = n; j >= i; j--)
}

我正在努力解决这个算法。我甚至不知道这个算法的时间复杂度是多少?我用在线软件检查过了，它只显示了0 (n)。

Answer 1

首先，算法应该是这样的:

for (i = 1; i <= n; i++)
for (j = n; j >= i; j--)
DoSomeWork(i, j); // <- Payload which is O(1)

要找出时间复杂度，让我们计算DoSomeWork将执行多少次:

i :    j : executed, times 
----------------------------
1 : 1..n : n
2 : 2..n : n - 1
3 : 3..n : n - 2
.. :  ...   ...  
n : n..n : 1

到目前为止一切顺利，DoSomeWork将被执行

n + n - 1 + n - 2 + ... + 2 + 1 = (n + 1) * n / 2 

;的时间复杂度是

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

嵌套循环不一定具有二次时间复杂度，例如

for (i = 1; i <= n; i++)
for (j = n; j >= i; j /= 2) // note j /= 2, instead of j--
DoSomeWork(i, j); 

具有O(n * log(n))时间复杂度

Answer 2

考虑一下。我们进入外循环多少次?n次,你肯定已经知道,因为我们有step1,……，步骤，总共n步。

我们有

n * average(inner)

在第一步中，内部循环有n步。然后它有n - 1步骤等等,在最后一步我们有1内循环的一步。

所以，内循环有:

n, n-1，…，在各自的迭代中执行1步。

由于加法既是交换的又是结合律，所以有:

(n + 1) + (n - 1 + 2) +…

等于(n+1)/2。

因为我们担心n ->无穷，加上1或者除以2就不那么重要了，所以我们大概有n * n个步骤，因此它的复杂度是O(n * n)，不要听工具说的，除非你有一些关于你的算法的额外信息要和我们分享。