<分区>
假设我有一个等式的递归:T(n)= T(n-2) + c .. 这意味着我们将问题的大小分解为 2 和这个算法的阶数是 O(n) 是对的!现在，假设我的等式变为，T(n)= T(n-2)+cn .. 为什么阶变为 n2(2 的次方)？我不想要任何递归树方法或任何其他方法来证明它变成了 n2 ..只要告诉我 c 和 cn 在这里有什么区别？
<分区>
假设我有一个等式的递归:T(n)= T(n-2) + c .. 这意味着我们将问题的大小分解为 2 和这个算法的阶数是 O(n) 是对的!现在，假设我的等式变为，T(n)= T(n-2)+cn .. 为什么阶变为 n2(2 的次方)？我不想要任何递归树方法或任何其他方法来证明它变成了 n2 ..只要告诉我 c 和 cn 在这里有什么区别？
最佳答案
Just tell me what does c and cn make the difference here ?
这意味着，额外的工作总是增加一个c (或在 T(n -2) + cn 的情况下为两个):
T(n) = T(n-1) + c
如果问题规模增加一，您需要投入的额外工作是c , 这是常数。
T(n) = T(n-1) + cn
如果问题大小增加一，您需要投入的额外工作就是一个c比上次将问题规模增加一倍。
即假设您从 n 增加了问题规模至 n + 1 , 添加了 10c的额外工作。当您现在从 n + 1 增加问题规模时至 n + 2 , 您将需要添加额外的 11c工作。
我们以这个系列结束:
d + c + 2c + 3c + 4c + 5c + ...
关于algorithm - 与递归混淆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12768532/