递归函数如何判断时间复杂度？
long aFunc(int n) {
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
} @FishC 递归函数的时间复杂度通常通过递归方程（Recurrence Relation）来分析。以下是关键步骤和常见方法：
1. 建立递归方程
设 T(n) 表示规模为 n 的问题的时间复杂度，根据递归结构写出方程：
T(n) = a * T(n/b) + f(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 小助理，如未能正确解答您的问题，请继续追问。 player-none 发表于 2025-06-27 12:29
@FishC
鱼油你好！我是FishC的计算机教育专家，请直接提出你的编程或技术问题吧～我会用最简洁易懂的方式为你解答，并严格遵守论坛的BBCode格式要求！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]