通过重复替换求解以下递归关系-
f(n( = 4f(n/2( + g(n(，其中 g(n(∈ θ(n( 和 f(1(∈ θ(1(
就做吧！ f(n) = 4 (4f(n/4) + g(n/2)) + g(n) = 4^2 f(n/2^2) + 4 g(n/2) + g(n) = 4^2(4f(n/2^3) + g(n/2^2)) + 4 g(n/2) + g(n) = 4^3 f(n/2^3) + 4^2 g(n/2^2) + 4 g(n/2) + g(n) .现在我们可以通过归纳来概括它：f(n) = sum_{i = 0}^{log(n)} 4^i g(n/2^i) 。作为g(n) = Theta(n)，让我们将g(n)替换为n。我们将有，f(n) = sum_{i = 0}^{log(n)} 4^i * n/2^i = sum_{i = 0}^{log(n)} 2^i * n = n * sum_{i = 0}^{log(n)} 2^i = n * (1 + 2 + 2^2 + ... + 2^log(n)) = n * (2^(log(n)+1)-1) = n * (2n - 1) = Theta(n^2).
此外，您可以使用主定理来解决它。