算法笔记

第一节 递归

1.1 概述

什么是递归？简单的说，一个方法自己调用自己即递归。递归实质上是把一个大问题分解为一个个小问题，然后通过一个个解决小问题最终解决大问题。

1.2 斐波那契数列

1.2.1 问题

斐波那契数列是典型的递归案例：

• F(0) = 0（初始值）
• F(1) = 1（初始值）
• 对于所有大于1的整数n：f(n) = f(n-1) + f(n-2)（递归定义）

除了开头0和1，每个数字都刚好等于前两个数字之和：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

1.2.2 实现

用代码来表示斐波那契数列：

class Solution {
    public int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

1.2.3 运行轨迹

但递归的时间开销实在是太高了，如下图所示，求F(n)要沿树走下去并依次执行返回上来，即4-3-2-1-2-0-3-1-4-2-1-2-0-2-4。

1.2.4 时间复杂度

递归过程即遍历二叉树的流程，所以所有节点耗时相加即总耗时。每个节点只做了求和操作即 O(1) ，所以总时间为 2^n 。

1.2.5 额外内存空间

空间复杂度是指算法运行期间所需占用的所有内存空间，而我们分析算法时更常用的是额外内存空间，两者区别：长度为 n 的数组排序， O(n) 的空间不会算在额外内存空间，因为这个空间是必要的，不是取决于你的算法的。

对于递归算法来说，每个节点所需空间为 O(1) ，总共需要 O(n) 的空间。

1.2.6 优化

可以明显的看出递归算法的低效主要是因为进行了大量的重复操作，只要减少不必要的重复操作就可以提高算法效率。

首先我们可以想到用一个数据结构来记录已经进行过的操作，每次操作前判断一下是否进行过来避免重复。

选用一个数组来存放对应下标的值，通过游标遍历到n求得对应值。

public int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int[] notes = new int[n+1];
    notes[0] = 0;
    notes[1] = 1;
    for(int i = 2; i <= n; i++) {
        notes[i] = notes[i-1] + notes[i-2];
    }
    return notes[n];
}

此时时间复杂度降低到了 O(n) 。

接着还可以继续优化空间，求第n个数的值最终并不需要我们记录之前的每个元素，所以可以继续优化。

public int fibonacci(int n) {
    int a = 0;
    int b = 1;
    if(n == 0) {
        return a;
    }
    if(n == 1) {
        return b;
    }
    for(int i = 2; i <= n; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    return b;
}

这样时间复杂度仍为 O(n) ，而空间也降到了 O(1) 。

这种解法其实就是动态规划。