递归关系式

概述

递归关系式 是用较小输入的函数值来定义函数值的等式或不等式。它是分析分治算法运行时间的核心数学工具，将算法的递归结构转化为可求解的数学表达式。

定义

递归关系式

递归关系式（递归式）是描述递归算法运行时间的等式或不等式。例如，归并排序的递归式为： $T(n)=\{\begin{array}{ll}\Theta (1)& \text{若 }n\le n_0\\ aT(n/b)+f(n)& \text{若 }n>n_0\end{array}$ 其中 $a\ge 1$ 是子问题个数，$b>1$ 是子问题规模缩小因子，$f(n)$ 是分解和合并的代价。

核心性质

• 递归式由递归项（如 $aT(n/b)$）和非递归项（如 $f(n)$）组成。
• 求解递归式即找到其渐近紧界（$\Theta$）、上界（$O$）或下界（$\Omega$）。
• CLRS提供三种主要求解方法：代入法（4.3）、递归树法（4.4）、主定理（4.5）。
• Akra-Bazzi方法（4.7）是主定理的推广，适用于更一般的递归形式。

章节扩展

第4章：分治策略

• 4.1 矩阵乘法：朴素分治矩阵乘法产生递归式 $T(n)=8T(n/2)+\Theta (n^2)$。
• 4.2 Strassen算法：改进分解后递归式变为 $T(n)=7T(n/2)+\Theta (n^2)$，复杂度降至 $O(n^{2.81})$。
• 4.3 代入法：通过猜测解并数学归纳证明来求解递归式。
• 4.4 递归树法：将递归式展开为树形结构，逐层求和。
• 4.5 主定理：提供分治递归式的封闭形式解。
• 4.7 Akra-Bazzi递归：处理非等分子问题的推广形式。

第6章：堆排序

• 6.2 维护堆性质 MAX-HEAPIFY的递归关系式：$T(n)\le T(2n/3)+\Theta (1)=O(\lg n)$
• 6.3 建堆 BUILD-MAX-HEAP的总时间分析

第7章：快速排序

• 7.2 快速排序的性能 四种场景的递归关系式（最坏 $\Theta (n^2)$、最好 $\Theta (n\lg n)$、平衡 $O(n\lg n)$）
• 7.4 快速排序的分析 最坏情况代入法证明、期望运行时间分析

第9章：中位数与序统计

• 9.3 最坏情况线性时间选择 SELECT的递归关系式：$T(n)\le T(\lceil n/5\rceil )+T(7n/10+6)+O(n)=O(n)$

参见

• 分治法
• 递归树
• 归并排序