代入法是一种用于求解递归算法时间复杂度的技术，它通过展开递归关系式、识别模式，然后利用数学归纳法来证明结果。
- 理解递归是如何工作的。
- 写出递归关系式。
- 根据递归模式猜测解。
- 利用数学归纳法验证猜测的解。
让我们通过下面的示例代码来理解上述步骤。
C++
CODEBLOCK_1e15bf1f
Java
CODEBLOCK_ff38670e
Python
CODEBLOCK_2c922485
C#
CODEBLOCK_937949d6
JavaScript
CODEBLOCK_7e39d3a2
理解此代码中的递归
- 每次调用该函数时，它都会打印一次
"GFG"。 - 它会进行两次递归调用，每次的输入规模都是
n/2。 - 当
n <= 0时，递归停止。
写出递归关系式
每个函数调用中完成的工作是常量级的（打印 INLINECODEa81c2d91），并且该函数进行了两次规模为 INLINECODE820cbb70 的递归调用。因此，递归关系式为： T(n) = 2T(n/2) + O(1)
应用代入法
为了猜测递归的解，我们分析该函数产生的递归调用次数。
每个函数调用只执行常量级的工作，并将问题拆分为两个规模为 n/2 的子问题。
随着递归的继续，函数调用的数量在每一层都会翻倍，并且当输入规模变为常量时递归停止，这大约发生在 log n 层之后。
因此，我们猜测时间复杂度为 T(n) = O(n)。
> 现在，我们来验证这个猜测。
> 假设对于某个常数 c > 0： T(n) ≤ cn
>
> 假设这对于较小的 n 值成立，特别是对于 n/2： T(n/2) ≤ c(n/2)
>
> 代入递归关系式：
> T(n) = 2T(n/2) + O(1)
> ≤ 2 · c(n/2) + O(1)
> = cn + O(1)
> 对于足够大的 n 值，常数项会被 cn 主导。
> 因此， T(n) ≤ cn
结果： 假设成立，这证实了该递归的时间复杂度为： T(n) = O(n)
归并排序示例
请参考 归并排序代码 作为下一个示例。在每次函数调用中，数组被分成两半，并进行了两次递归调用，每次都在大小为 n/2 的子数组上操作。在递归调用之后，函数执行线性工作来合并这两个已排序的半部分。因此，递归关系式为： T(n) = 2T(n/2) + n
应用代入法
为了猜测递归的解，我们分析函数在递归的每一层所做的工作。每个函数调用将数组分为两个大小为 n/2 的子数组并进行两次递归调用。在递归调用返回后，函数执行线性工作来合并这两个已排序的半部分。
随着递归的进行，子问题的数量在每一层都翻倍，而每个子问题的规模则减半。当子数组大小变为常量时递归停止，这大约发生在 log n 层之后。在递归树的每一层，完成的总工作量都与 n 成正比。
因此，我们猜测时间复杂度为： T(n) = O(n log n)
> 验证猜测：
>
> 假设对于某个常数 c > 0： T(n) ≤ c n log n
> 假设这对于较小的 n 值成立，特别是对于 n/2： T(n/2) ≤ c (n/2) log(n/2)
> 代入递归关系式：
> T(n) = 2T(n/2) + n
> ≤ 2 ⋅ c (n/2) log(n/2) + n
> = cn (log n – log 2) + n
> = cn log n – cn + n
>
> 对于足够大的 n 值，线性项会被 cn log n 主导。
> 因此， T(n) ≤ cn log n
结果： 假设成立，这证实了该递归的时间复杂度为： T(n) = O(n log n)