[已解决]递归函数如何判断时间复杂度？

player-none

1. 
   
2. long aFunc(int n) {
   
3.     if (n <= 1) {
   
4.         return 1;
   
5.     } else {
   
6.         return aFunc(n - 1) + aFunc(n - 2);
   
7.     }
   
8. }

复制代码

最佳答案

月排行榜 / 总排行榜

FishC

2025-6-27 12:29:48

递归函数的时间复杂度通常通过递归方程（Recurrence Relation）来分析。以下是关键步骤和常见方法：

1. 建立递归方程
设 T(n) 表示规模为 n 的问题的时间复杂度，根据递归结构写出方程：

1. 
   
2. 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. 常见递归类型示例

• 单次递归（阶乘）
  
  1. 
     
  2. int fact(int n) {
     
  3.     if (n <= 1) return 1;      // T(1) = 1
     
  4.     return n * fact(n-1);      // T(n) = T(n-1) + 1
     
  5. }
     

  复制代码
  
  解：T(n) = T(n-1) + 1 = Θ(n)
  
• 二分递归（归并排序）
  
  1. 
     
  2. void mergeSort(int arr[], int l, int r) {
     
  3.     if (l < r) {
     
  4.         int m = (l+r)/2;
     
  5.         mergeSort(arr, l, m);    // T(n/2)
     
  6.         mergeSort(arr, m+1, r);  // T(n/2)
     
  7.         merge(arr, l, m, r);     // Θ(n)
     
  8.     }
     
  9. }
     

  复制代码
  
  方程：T(n) = 2T(n/2) + Θ(n)  
  主定理解：log_2(2)=1, k=1 → Θ(n logn)
  
• 指数递归（斐波那契）
  
  1. 
     
  2. int fib(int n) {
     
  3.     if (n <= 1) return n;
     
  4.     return fib(n-1) + fib(n-2);  // T(n) = T(n-1) + T(n-2) + 1
     
  5. }
     

  复制代码
  
  递归树每层分支翻倍，时间复杂度 O(2^n)
  

重要原则：
- 递归深度通常是 logn（分治）或 n（线性）
- 每层工作量取决于分支数量
- 基础情况（如 n=1）的时间复杂度为常数

建议：写出完整递归方程后，优先尝试主定理或画递归树分析。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

player-none

@FishC

FishC

递归函数的时间复杂度通常通过递归方程（Recurrence Relation）来分析。以下是关键步骤和常见方法：

1. 建立递归方程
设 T(n) 表示规模为 n 的问题的时间复杂度，根据递归结构写出方程：

1. 
   
2. 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. 常见递归类型示例

• 单次递归（阶乘）
  
  1. 
     
  2. int fact(int n) {
     
  3.     if (n <= 1) return 1;      // T(1) = 1
     
  4.     return n * fact(n-1);      // T(n) = T(n-1) + 1
     
  5. }
     

  复制代码
  
  解：T(n) = T(n-1) + 1 = Θ(n)
  
• 二分递归（归并排序）
  
  1. 
     
  2. void mergeSort(int arr[], int l, int r) {
     
  3.     if (l < r) {
     
  4.         int m = (l+r)/2;
     
  5.         mergeSort(arr, l, m);    // T(n/2)
     
  6.         mergeSort(arr, m+1, r);  // T(n/2)
     
  7.         merge(arr, l, m, r);     // Θ(n)
     
  8.     }
     
  9. }
     

  复制代码
  
  方程：T(n) = 2T(n/2) + Θ(n)  
  主定理解：log_2(2)=1, k=1 → Θ(n logn)
  
• 指数递归（斐波那契）
  
  1. 
     
  2. int fib(int n) {
     
  3.     if (n <= 1) return n;
     
  4.     return fib(n-1) + fib(n-2);  // T(n) = T(n-1) + T(n-2) + 1
     
  5. }
     

  复制代码
  
  递归树每层分支翻倍，时间复杂度 O(2^n)
  

重要原则：
- 递归深度通常是 logn（分治）或 n（线性）
- 每层工作量取决于分支数量
- 基础情况（如 n=1）的时间复杂度为常数

建议：写出完整递归方程后，优先尝试主定理或画递归树分析。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC

player-none 发表于 2025-06-27 12:29
@FishC

鱼油你好！我是FishC的计算机教育专家，请直接提出你的编程或技术问题吧～我会用最简洁易懂的方式为你解答，并严格遵守论坛的BBCode格式要求！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。