T(n-1)的时间复杂度

问题描述

我很困惑于解决这个时间复杂性问题.

I am confused on solving this time complexity problem.

T(n) = T(n-1)

我知道在最坏的情况下T(n) = T(n-1) + T(1) + n

I know in quick-sort worst case T(n) = T(n-1) + T(1) + n

评估为(n-1) + (n-2) + (n-3) + ... + 1&这个几何序列等于O(n^2)

Which evaluates to (n-1) + (n-2) + (n-3) + ... + 1 & this geometric sequence equals O(n^2)

但是.我在stackoverflow上看到的答案是T(n) = T(n-1) + c = O(n).

However. I see answers on stackoverflow that say T(n) = T(n-1) + c = O(n).

当它也等于(n-1) + (n-2) + (n-3) + ... + 1等于O(n^2)

有人可以解释一下吗.

推荐答案

T(n) = T(n-1) + c不等于(n-1) + (n-2) + (n-3) + ... + 1，因为要添加的术语是常量.基本上:

T(n) = T(n-1) + c isn't equal to (n-1) + (n-2) + (n-3) + ... + 1 because the terms being added are constants. Basically:

未添加任何内容:

T(n) = T(n-1)
0 + 0 + 0 + ... + 0 = 0
O(1)

添加常量:

T(n) = T(n-1) + c
c + c + c + ... + c = nc
O(n)

添加变量:

T(n) = T(n-1) + n
1 + 2 + 3 + ... + n = n(n+1)/2
O(n^2)

这篇关于T(n-1)的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！