我对解决这个时间复杂度问题感到困惑。
T(n) = T(n-1)
我知道在快速排序最坏的情况下T(n) = T(n-1) + T(1) + n
其评估结果为(n-1) + (n-2) + (n-3) + ... + 1
& 这个几何数列等于O(n^2)
然而。我在 stackoverflow 上看到答案说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)
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)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)