T(n)> = T(n-1)总是正确吗？

Question

我看到了一个证明找到排序算法复杂性的证明,其中说明了这样的事情:

Total time complexity for the algorithm = T(n-1) + T(n-2)

Thus, Total time complexity for the algorithm <= 2 * T( n-2 )

并进一步证明了某种关系.

问:我能安全地假设T(n) >= T(n-1)吗？当我已经在尝试证明某些算法的复杂性时,我怎么能提前做出这个声明呢？

Answer 1

不,你不能做这样的说法.

考虑一个功能:

f(0) = 1000000! (factorial of 1000000)
f(n) = 1, for n>0

这里,具有较大参数的函数的时间复杂度小于较低的函数.

一切都取决于细节,特别是 - 在提供的示例中,您已经有了一个声明

Total time complexity for the algorithm = T(n-1) + T(n-2)

这相当于

T(n) = T(n-1) + T(n-2)

这是对复杂性的强烈主张,但似乎并不正确

Thus, Total time complexity for the algorithm <= 2 * T( n-2 )

正如我们可以推断的那样

T(n) = T(n-1) + T(n-2)

那

T(n) = T(n-1) + T(n-2) = (T(n-2) + T(n-3)) + T(n-2) >= 2 * T( n-2 )

也许声称是这个？

Thus, Total time complexity for the algorithm >= 2 * T( n-2 )