我看到了一个发现排序算法复杂性的证明，它是这样说的：
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)吗？当我已经在尝试证明某些算法的复杂性时，我该如何事先提出这个主张？
问问题
182 次
4 回答
6
不，你不能提出这样的要求。
考虑一个函数：
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 )
于 2013-08-11T07:21:20.877 回答
2
不，你不能总是做出这个假设，它取决于函数 T。
例如：
T(0) = T(1) = 1 //no important
T(2n) = T(2n-2) //all even numbers are calculated recursivel
T(2n+1) = 1 //all odd numbers
在上面，对于每个奇数n：T(n) < T(n-1)
这实际上可能是一个复杂函数的一个实际示例是如果n必须是偶数，如果不是 - 返回错误。
于 2013-08-11T07:21:38.870 回答
0
不，取决于算法。
我可以定义这样的算法：对于每个大小的输入n < 1000尝试做一些事情。如果n > 1000返回一些决定性的决定。
所以对于每个n < 1000人来说，可能会有一个漫长而累人n > 1000的计算，但对于O(1)
于 2013-08-11T07:22:52.723 回答
0
T(n) >= 2*T(n-2)是隐含的，对于n>3，由递归关系T(n) = T(n-1)+T(n-2)。
T(n-1)是T(n-2)+T(n-3)。
如果T表示算法的成本，则不能为负。
T(n-3) >= 0意味着T(n-1) >= T(n-2)和T(n) >= 2*T(n-2)。
这只是特定递归关系的结果，而不是您通常可以假设的结果，尽管算法分析中出现的许多递归关系都是如此。
于 2013-08-11T09:08:33.283 回答