This doesn't make sense as a real-world recurrence relationship. T(n) denotes the runtime to solve a problem of size n; T(n-1) denotes the runtime for size (n-1). Given that you must solve the problem for size (n-1) before you can solve for size n (otherwise it wouldn't be a recursion), the runtime must necessarily be monotonic as n increases.
However, your expression oscillates up and down with n; this doesn't make sense.
The only way this expression could ever make sense is if we assume that T(n) is constant with n, so that there is no oscillation. It turns out that there is a constant value that allows this to happen, just set T(n) = T(n-1), and solve. (Note that this is equally meaningless; we don't generally talk about absolute values of T(n).)
发布评论
评论（1）
扩展我上面的评论...
这作为现实世界的递归关系没有意义。
T(n)表示解决大小为n的问题的运行时；T(n-1)表示大小(n-1)的运行时间。鉴于您必须先解决大小(n-1)的问题，然后才能解决大小n的问题（否则就不是递归），运行时必须随着n的增加，单调。然而，你的表情随着
n上下摆动；这没有道理。该表达式有意义的唯一方法是假设
T(n)对于n是恒定的，这样就不会出现振荡。事实证明，有一个常数值允许这种情况发生，只需设置 T(n) = T(n-1)，然后求解即可。 （请注意，这同样没有意义；我们通常不会谈论T(n)的绝对值。）Expanding on my comments above...
This doesn't make sense as a real-world recurrence relationship.
T(n)denotes the runtime to solve a problem of sizen;T(n-1)denotes the runtime for size(n-1). Given that you must solve the problem for size(n-1)before you can solve for sizen(otherwise it wouldn't be a recursion), the runtime must necessarily be monotonic asnincreases.However, your expression oscillates up and down with
n; this doesn't make sense.The only way this expression could ever make sense is if we assume that
T(n)is constant withn, so that there is no oscillation. It turns out that there is a constant value that allows this to happen, just setT(n) = T(n-1), and solve. (Note that this is equally meaningless; we don't generally talk about absolute values ofT(n).)