我看到了一个关于寻找排序算法复杂性的证明，它是这样说的:
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) 吗？当我已经在尝试证明某些算法的复杂性时，我如何才能事先提出这一主张？
最佳答案
不，您不能提出这样的 claim 。
考虑一个函数:
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 )
关于algorithm - T(n) >= T(n-1) 总是正确的吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18169633/