假设我有一个等式的递归：T(n)= T(n-2) + c..这意味着我们将问题大小分解为 2 倍，并且该算法的顺序是 O(n)，这是正确的！现在，假设我的方程变成T(n)= T(n-2)+cn了，.. 为什么阶数变成 n2（2 次方）？我不想要任何递归树方法或任何其他方法来证明它变成 n2 .. 告诉我这里有什么作用c和cn不同之处？
问问题
109 次
1 回答
1
请告诉我 c 和 cn 在这里有什么不同？
这意味着，额外的工作总是增加一c（或在 的情况下增加二T(n -2) + cn）：
T(n) = T(n-1) + c
如果问题大小增加 1，则需要投入的额外工作是c，这是恒定的。
T(n) = T(n-1) + cn
如果问题大小增加 1，那么您需要投入的额外工作c比您上次将问题大小增加 1 时多 1。
即假设您将问题大小从n增加到n + 1，这增加10c了额外的工作。当您现在将问题大小从n + 1增加到 时n + 2，您将需要添加额外11c的工作。
我们结束了这个系列：
d + c + 2c + 3c + 4c + 5c + ...
于 2012-10-07T13:39:51.567 回答