彻底搞懂递归的时间复杂度

彻底搞懂递归的时间复杂度

引用

CSDN

1.

https://blog.csdn.net/pengfeicfan/article/details/120299868

掌握算法时间复杂度是区分优秀程序员的重要标志。本文通过两个经典面试题，深入解析递归算法的时间复杂度计算方法。

泰波那契序列问题

泰波那契序列 Tn 定义如下：

• T0 = 0, T1 = 1, T2 = 1
• 在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给定整数 n，返回第 n 个泰波那契数 Tn 的值。

示例：

• 输入：n = 4
• 输出：4
• 解释：
• T_3 = 0 + 1 + 1 = 2
• T_4 = 1 + 1 + 2 = 4

示例：

• 输入：n = 25
• 输出：1389537

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

初学者可能会写出以下递归解法：

const tribonacci = (n) => {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 1;
  }
  return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
};

但这种解法会超时，其时间复杂度并非 O(logn)。递归算法的时间复杂度取决于递归次数和每次递归的操作次数。

求 x 的 n 次方问题

考虑求 x 的 n 次方的算法。最直观的解法是使用 for 循环：

int function1(int x, int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

时间复杂度为 O(n)。面试官可能会要求优化算法，使用递归：

int function2(int x, int n) {
    if (n == 0) {
        return 1;
    }
    return function2(x, n - 1) * x;
}

这个递归解法的时间复杂度仍然是 O(n)，因为递归了 n 次，每次进行一次乘法操作。

进一步优化的递归解法：

int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n/2) * function3(x, n/2)*x;
    }
    return function3(x, n/2) * function3(x, n/2);
}

分析其时间复杂度，可以将其抽象为一颗满二叉树。对于 n = 16 的情况：

这棵树的节点数量为 2^3 + 2^2 + 2^1 + 2^0 = 15，即等比数列求和。因此，时间复杂度为 O(n)。

最终优化的 O(logn) 解法：

int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n/2);
    if (n % 2 == 1) {
        return t*t*x;
    }
    return t*t;
}

这个解法每次递归都将问题规模减半，时间复杂度为 O(logn)。

主定理

主定理是用于计算所有递归函数时间复杂度的重要工具。它可以帮助我们分析以下几种常见递归场景的时间复杂度：

1. 二分查找（Binary search）：时间复杂度为 O(logn)
2. 二叉树遍历（Binary tree traversal）：时间复杂度为 O(n)
3. 二维矩阵搜索（Optimal sorted matrix search）：时间复杂度为 O(n)
4. 归并排序（Merge sort）：时间复杂度为 O(nlogn)

总结

递归算法的时间复杂度可以通过递归树或主定理来计算。理解递归的时间复杂度对于编写高效算法至关重要。建议多做相关练习以加深理解。

课后作业

1. 分析以下阶乘算法的时间复杂度：

int fact(int n){
    if (n<=l) return 1;
    return n*fact(n-1);
}

2. 编写一个算法，计算数组中的逆序对数量：

/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
    // 请完成代码
};

示例：

• 输入：[7,5,6,4]
• 输出：5
• 限制：0 <= 数组长度 <= 50000