ericpuwang

递归算法的复杂度分析

本篇讲通过求斐波那契数列和二分法来深入分析一波递归算法的时间和空间复杂度。

时间复杂度本质：递归的次数 * 每次递归的时间复杂度
空间复杂度本质：递归的深度 * 每次递归的空间复杂度

斐波那契数列

int fibonacci(int i)
{
    if(i <= 0) return 0;
    if(i == 1) return 1;
    return fibonacci(i-1) + fibonacci(i-2);
}

时间复杂度分析

每次递归的时间复杂度都是O(1), 再看看递归次数。以i=5为例，将递归过程抽象成一颗树: 斐波那契_时间复杂度

从图中可以看出f(5)是又f(4)和f(3)相加而来，那么f(4)是又f(3)和f(2)相加得到。以此类推在这颗二叉树中每一个结点都是一次递归，那么这棵树有多少个结点呢？一棵深度（按根节点深度为1）为k的二叉树最多可以有 2^k - 1 个节点。所以该递归算法的时间复杂度是O(2^n)

代码优化

// 版本二
// 这里相当于用first和second来记录当前相加的两个数值，此时就不用两次递归了。
int fibonacci(int first, int second, int n) {
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci(second, first + second, n - 1);
    }
}

因为每次递归的时候n减1，即只是递归了n次，所以时间复杂度是O(n)。同理递归的深度依然是n，每次递归所需的空间也是常数，所以空间复杂度依然是O(n)。故该版本的复杂度如下:

时间复杂度O(n)
空间复杂度O(n)

空间复杂度分析

A: 为什么要求递归的深度呢？ Q: 因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

从代码中可以看到每次递归所需的空间大小一样，所以每次递归时需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度是O(n) 递归的深度如下图所示：斐波那契_空间复杂度递归第n个斐波那契数的话，递归调用栈的深度就是n。那么每次递归的空间复杂度是O(1)，调用栈深度为n，所以这段递归代码的空间复杂度就是O(n)。最后对各种求斐波那契数列方法的性能做一下分析，如题： | 求斐波那契数列 | 时间复杂度 | 空间复杂度 | | :— | :— | :— | | 非递归 | $O(n)$ | $O(1)$ | | 递归算法 | $O(2^n)$ | $O(n)$ | | 优化递归算法 | $O(n)$ | $O(n)$ |

可以看出，求斐波那契数的时候，使用递归算法并 不一定是在性能上是最优的 ，但递归确实 简化的代码层面的复杂度 。

二分法

int binary_search( int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}

时间复杂度是 $O(log_2n)$
空间复杂度分析: 我们依然看 每次递归的空间复杂度和递归的深度 每次递归的空间复杂度可以看出主要就是参数里传入的这个arr数组，但需要注意的是在C/C++中函数传递数组参数，不是整个数组拷贝一份传入函数而是传入的数组首元素地址。也就是说每一层递归都是公用一块数组地址空间的，所以每次递归的空间复杂度是常数即：O(1)。再来看递归的深度，二分查找的递归深度是 $O(log_2n)$ ，递归深度就是调用栈的长度，那么这段代码的空间复杂度为 $1 * log_2n = O(log_2n)$。

** 注意自己所用的语言在传递函数参数的时，是拷贝整个数值还是拷贝地址，如果是拷贝整个数值那么该二分法的空间复杂度就是O(nlog_2n)。**