递归算法的时间复杂度 每次递归取 O(N)

Question

我有一个算法，伪代码如下：

def foo(n):
if n == 0
return;
// Loop below take O(N)
for(i=0; i<n:i++){
.... 
}
foo(n-1):

这个想法是每个递归需要 n 个时间，并且有 n 个递归。

总时间应该像 1 + 2 3 + 4 +5 + ... +n

可以证明为 O(n*n(吗？

Answer 1

是的，它O(n^2).

n自然数之和为：n * (n+1) / 2，链接。这与常数因子的n^2不同，所以O(n * (n+1) / 2) == O(n^2)

Answer 2

首先，您在for循环中有n次迭代，然后函数将以n-1，n-2， ...， 0 重复。

很容易看出n + (n-1) + (n-2) + ... + 1 = (n+1) * n/2 = (n^2 + n)/2 = O(n^2).

要评估大O，即最坏情况的复杂性，请记住，您必须忽略所有系数，常数和低幂项：

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