如何用代换法分析递归

一般情况下，利用代换法分析递归可分为三个步骤，分别是猜测、假设、以及代换。

以递归式 T(n) = 4T(n/2) + n 为例，首先要猜测其运行时间，这里我们姑且认为他的运行时间为 O(n^3)。

然后我们需要假设 T(k) <= c*k^3 c 为常数且 k < n 。

然后代换，T(n) = 4*c*(n/2)^3 + n 。化简得，T(n) = (1/2)*c*n^3 + n 。我们需要接着证明算式 T(n) <= c*n^3 。 故接着化简 T(n) 为 c*n^3 - [(1/2)*c*n^3 - n] 。只要 [(1/2)*c*n^3 - n] >= 0（即 c >= 1，n >= 1），T(n) <= c*n^3 成立（即 T(n) = θ(n^3)）。