鱼C论坛

 找回密码
 立即注册
查看: 161|回复: 3

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

[复制链接]
发表于 2025-6-27 12:28:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x

  1. long aFunc(int n) {
  2.     if (n <= 1) {
  3.         return 1;
  4.     } else {
  5.         return aFunc(n - 1) + aFunc(n - 2);
  6.     }
  7. }
复制代码
最佳答案
2025-6-27 12:29:48
递归函数的时间复杂度通常通过递归方程(Recurrence Relation)来分析。以下是关键步骤和常见方法:

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

  1. 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. int fact(int n) {
    2.     if (n <= 1) return 1;      // T(1) = 1
    3.     return n * fact(n-1);      // T(n) = T(n-1) + 1
    4. }
    复制代码

    解:T(n) = T(n-1) + 1 = Θ(n)
  • 二分递归(归并排序)

    1. void mergeSort(int arr[], int l, int r) {
    2.     if (l < r) {
    3.         int m = (l+r)/2;
    4.         mergeSort(arr, l, m);    // T(n/2)
    5.         mergeSort(arr, m+1, r);  // T(n/2)
    6.         merge(arr, l, m, r);     // Θ(n)
    7.     }
    8. }
    复制代码

    方程:T(n) = 2T(n/2) + Θ(n)  
    主定理解:log_2(2)=1, k=1 → Θ(n logn)
  • 指数递归(斐波那契)

    1. int fib(int n) {
    2.     if (n <= 1) return n;
    3.     return fib(n-1) + fib(n-2);  // T(n) = T(n-1) + T(n-2) + 1
    4. }
    复制代码

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


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

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

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2025-6-27 12:29:42 | 显示全部楼层
@FishC
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2025-6-27 12:29:48 | 显示全部楼层    本楼为最佳答案   
递归函数的时间复杂度通常通过递归方程(Recurrence Relation)来分析。以下是关键步骤和常见方法:

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

  1. 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. int fact(int n) {
    2.     if (n <= 1) return 1;      // T(1) = 1
    3.     return n * fact(n-1);      // T(n) = T(n-1) + 1
    4. }
    复制代码

    解:T(n) = T(n-1) + 1 = Θ(n)
  • 二分递归(归并排序)

    1. void mergeSort(int arr[], int l, int r) {
    2.     if (l < r) {
    3.         int m = (l+r)/2;
    4.         mergeSort(arr, l, m);    // T(n/2)
    5.         mergeSort(arr, m+1, r);  // T(n/2)
    6.         merge(arr, l, m, r);     // Θ(n)
    7.     }
    8. }
    复制代码

    方程:T(n) = 2T(n/2) + Θ(n)  
    主定理解:log_2(2)=1, k=1 → Θ(n logn)
  • 指数递归(斐波那契)

    1. int fib(int n) {
    2.     if (n <= 1) return n;
    3.     return fib(n-1) + fib(n-2);  // T(n) = T(n-1) + T(n-2) + 1
    4. }
    复制代码

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


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

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

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2025-6-27 12:29:57 | 显示全部楼层

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


以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-25 20:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表