《趣学算法》阅读笔记（一）

空间复杂度： 算法运行占用的空间大小，一般讲算法的辅助空间，作为空间复杂度的度量标准。
这个其实很好理解，就不多说了，一个算法执行所占的空间实际上有输入输出占用的空间、辅助变量占用的空间、算法本身占用的空间，和时间复杂度量化一样，一般我们仅考虑辅助空间占用情况，来作为空间复杂度的度量标准。

1.2 斐波那契数列的进化

现实的算法问题：

• 兔子序列问题：假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？
• 花瓣、叶子序列问题：观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花
  的花瓣，可以发现它们的花瓣数目为斐波那契数：3，5，8，13，21，…，难道这些植物懂得斐波那契数列吗？应该并非如此，它们只是按照自然的规律才进化成这样的。这似乎是植物排列种子的“优化方式”，它能使所有种子具有相近的大小却又疏密得当，不至于在圆心处挤太多的种子而在圆周处却又很稀疏。
  这里我们以兔子问题，来一步一步优化解决斐波那契数列问题。
  
  这个数列有十分明显的特点，从第3个月开始，当月的兔子数=上月兔子数+当月新生
  兔子数，而当月新生的兔子正好是上上月的兔子数。因此，前面相邻两项之和，构
  成了后一项，即：
  当月的兔子数=上月兔子数+上上月的兔子数
  斐波那契数列如下：
  1，1，2，3，5，8，13，21，34，…
  递归式表达式：
  

1.2.1 第一种解法（递归）

import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str_0 = scan.nextLine().trim();
		int n = Integer.parseInt(str_0);
		System.out.println(fib1(n));
		scan.close();
	}

	/**
	 * 递归解法
	 * 
	 * @Title: fib1
	 * @Description:
	 * @author: itbird
	 * @date 2022年10月19日 上午10:08:57
	 * @param n
	 * @return int 时间复杂度: O(指数级) 空间复杂度: O(N)
	 */
	public static int fib1(int n) {
		if (n < 1) {
			return -1;
		}
		if (n == 1 || n == 2) {
			return 1;
		} else {
			return fib1(n - 1) + fib1(n - 2);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

所以我们需要改进。

1.2.2 第二种解法（优化时间复杂度，以空间换时间）

既然递归解法，时间复杂度太高，那么我们想办法，通过空间换时间

import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str_0 = scan.nextLine().trim();
		int n = Integer.parseInt(str_0);
//		System.out.println(fib1(n));
		System.out.println(fib2(n));
		scan.close();
	}

	/**
	 * 既然递归解法，时间复杂度太高，那么我们想办法，通过空间换时间
	 * 
	 * @Title: fib2
	 * @Description:
	 * @author: itbird
	 * @date 2022年10月19日 上午10:20:59
	 * @param n
	 * @return int 时间复杂度: O(N) 空间复杂度: O(N)
	 */
	public static int fib2(int n) {
		if (n <= 2) {
			return 1;
		}
		int[] nums = new int[n];
		nums[0] = 1;
		nums[1] = 1;
		for (int i = 2; i < nums.length; i++) {
			nums[i] = nums[i - 1] + nums[i - 2];
		}
		return nums[n - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

大家发现，这个算法的确可以解决时间复杂度的问题，而且输入50以上的n时，都可以很快得出结论，但是当输入的数字很大时，运行过程中，可能出现了内存溢出的问题。
仔细想想，这个算法中存在的缺点是，实际上我们仅仅需要nums[i] 、 nums[i - 1] 、 nums[i - 2]三个值，过程中的值，不需要保存，那么下一步优化，就优化这个方向。

1.2.3 第三种解法（优化时间&空间）

import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str_0 = scan.nextLine().trim();
		int n = Integer.parseInt(str_0);
		// System.out.println(fib1(n));
		// System.out.println(fib2(n));
		System.out.println(fib3(n));
		scan.close();
	}

	/**
	 * 解决算法2中，空间利用率低的问题
	 * 
	 * @Title: fib3
	 * @Description:
	 * @author: itbird
	 * @date 2022年10月19日 上午10:21:39
	 * @param n
	 * @return int 时间复杂度: O(N) 空间复杂度: O(1)
	 */
	public static int fib3(int n) {
		if (n <= 2) {
			return 1;
		}
		int nums1 = 1;
		int nums2 = 1;
		int nums3 = 0;
		for (int i = 2; i < n; i++) {
			nums3 = nums1 + nums2;
			nums2 = nums1;
			nums1 = nums3;
		}
		return nums3;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38