算法笔记

算法笔记

第一节 递归

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 实现

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

1
2
3
4
5
6
7
8
9
10
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求得对应值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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个数的值最终并不需要我们记录之前的每个元素,所以可以继续优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

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