|
发表于 2025-6-27 12:29:48
|
显示全部楼层
本楼为最佳答案
递归函数的时间复杂度通常通过递归方程(Recurrence Relation)来分析。以下是关键步骤和常见方法:
1. 建立递归方程
设 T(n) 表示规模为 n 的问题的时间复杂度,根据递归结构写出方程:
其中:
- a:子问题数量
- n/b:子问题规模
- f(n):合并子问题的代价
2. 求解递归方程(常用方法)
方法一:主定理(Master Theorem)
适用于 T(n) = aT(n/b) + Θ(n^k) 的形式:
- 若 log_b(a) > k,则 T(n) = Θ(n^{log_b(a)})
- 若 log_b(a) = k,则 T(n) = Θ(n^k * logn)
- 若 log_b(a) < k,则 T(n) = Θ(n^k)
方法二:递归树(Recursion Tree)
方法三:代入法(Substitution)
3. 常见递归类型示例
- 单次递归(阶乘)
- int fact(int n) {
- if (n <= 1) return 1; // T(1) = 1
- return n * fact(n-1); // T(n) = T(n-1) + 1
- }
复制代码
解:T(n) = T(n-1) + 1 = Θ(n)
- 二分递归(归并排序)
- void mergeSort(int arr[], int l, int r) {
- if (l < r) {
- int m = (l+r)/2;
- mergeSort(arr, l, m); // T(n/2)
- mergeSort(arr, m+1, r); // T(n/2)
- merge(arr, l, m, r); // Θ(n)
- }
- }
复制代码
方程:T(n) = 2T(n/2) + Θ(n)
主定理解:log_2(2)=1, k=1 → Θ(n logn)
- 指数递归(斐波那契)
- int fib(int n) {
- if (n <= 1) return n;
- return fib(n-1) + fib(n-2); // T(n) = T(n-1) + T(n-2) + 1
- }
复制代码
递归树每层分支翻倍,时间复杂度 O(2^n)
重要原则:
- 递归深度通常是 logn(分治)或 n(线性)
- 每层工作量取决于分支数量
- 基础情况(如 n=1)的时间复杂度为常数
建议:写出完整递归方程后,优先尝试主定理或画递归树分析。
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。 |
|