【漫画算法 · 第一章】“算法的概述” 读书报告
目录
一、算法与数据结构
什么是算法？
在数学领域中，算法是用于解决某一类问题的公式和思想。而在计算机科学领域中，算法的本质是一系列程序指令，用于解决特定的运算和逻辑问题的，本系列文章的重点也是在此方面。但是在宏观上来看，不管是在数学领域还是在计算机科学领域的算法都是有很多相通的地方。
算法有简单，也有复杂；算法有高效，也有拙劣。其中，衡量算法的好坏的重要标准主要有两个：时间复杂度和空间复杂度。算法可以用在数学运算、数据和信息的查找、网站中内容的排序、找出最优决策等，非常重要。
什么是数据结构
数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
数据结构主要有以下几种组成方式：线性结构（最简单的数据结构，包括数组、链表以及衍生出来的栈、队列、哈希表）、树（相对复杂的数据结构，包括二叉树、二叉树堆之类的数据结构）、图（更为复杂的数据结构，呈现出多对多的关联关系）。其实数据结构的组成方式远不止这几种的，还有跳表、哈希链表、位图等千奇百怪的数据结构，但是他们实质上都是由基本的数据结构变形而来的。
二、时间复杂度
基本操作执行次数
下面用四个常见的场景+代码来讲述代码的基本操作执行次数（以下的T（n）为程序基本操作执行次数的函数，也可以认为是程序的相对执行时间函数）：
场景一：桌子上有n个蛋糕，张三吃一个所需的时间是5分钟，试问吃完所需的总时间是多少？
很明显，答案就是5*n=5n分钟，用函数表达式来描述的话就可以记作：T（n）=5n。用代码类似表示可以是：
import java.util.Scanner;
public class TestDemo {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
eat1(n);
sc.close();
}
public static void eat1(int n){
for (int i = 0; i < n; i++) {
System.out.println("第一分钟");
System.out.println("第二分钟");
System.out.println("第三分钟");
System.out.println("第四分钟");
System.out.println("第五分钟");
}
}
}该段代码T（n）=5n，执行次数是线性的。
场景二：桌子上有n个蛋糕，张三每5分钟吃掉一半数量的蛋糕（就比如有16个蛋糕，第5分钟吃掉8个，第10分钟吃掉4个，第15分钟吃掉2个……），那么张三最后吃剩一个蛋糕的时候，花了多少时间？
此类型为对数增长模式，所以对于本场景来说，T（n）=5logn。用代码类似表示可以是：
import java.util.Scanner;
public class TestDemo {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
eat2(n);
sc.close();
}
public static void eat2(int n) {
for (int i = n; i > 1; i/=2) {
System.out.println("第一分钟");
System.out.println("第二分钟");
System.out.println("第三分钟");
System.out.println("第四分钟");
System.out.println("第五分钟");
}
}
}该段代码T（n）=5logn，执行次数是用对数计算的。
场景三：桌子上有一个蛋糕和n个面包，张三吃掉一个蛋糕需要用5分钟，试问张三吃掉全部蛋糕需要多少时间呢？
这个问题一开始看会觉得好“弱智”，但其实其中包含了最简单的操作执行次数相关的东西。对于这道题，我们都可以知道，无论面包有多少个，吃掉全部的蛋糕的时间都是5分钟，和面包没有任何关系，所以，T（n）=5。用代码类似表示可以是：
import java.util.Scanner;
public class TestDemo {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
eat3(n);
sc.close();
}
public static void eat3(int n) {
System.out.println("第一分钟");
System.out.println("第二分钟");
System.out.println("第三分钟");
System.out.println("第四分钟");
System.out.println("第五分钟");
}
}该段代码T（n）=5，执行次数是常量。
场景四：桌子上有10个蛋糕，张三第一个蛋糕吃1分钟，第二个蛋糕吃2分钟，第三个蛋糕吃3分钟……以此类推，每吃一个蛋糕所花的时间就比上一个蛋糕多使用一分钟，试问张三吃完所有蛋糕需要花多少时间？
这个问题实际上就是问从1累加到10的总和是多少，根据搞死算法，其实就不难得出：T（n）=0.5n^2+0.5n。用代码类似表示可以是：
import java.util.Scanner;
public class TestDemo {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
eat4(n);
sc.close();
}
public static void eat4(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
System.out.println("吃蛋糕中");
}
System.out.println("吃一个蛋糕");
}
}
}该代码T（n）=0.5n^2+0.5n，执行次数是用多项式计算的。
渐进时间复杂度
如果存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))（被称为大O表示法），O为算法的渐进时间复杂度，简称为时间复杂度。
上面的引用内容算是对时间复杂度的定义，下面通过之前的四个场景来谈谈如何算出时间复杂度，当然，在计算时间复杂度之前应该先来看看计算时间复杂度的三个原则：
1.如果运行时间是常量数量级，则用常数1表示
2.只保留时间函数中的最高阶项
3.如果最高阶项存在，则省去最高阶项前面的系数
回顾场景一：T（n）=5n，最高阶项为5n，就可以省去前面系数5，所以转化之后的时间复杂度为O（n）。
回顾场景二：T（n）=5logn，最高阶项为5logn，省去前面系数5，所以转化之后的时间复杂度为O（logn）。
回顾场景三：T（n）=5，只有常数量级，所以转化之后的时间复杂度为O（1）。
回顾场景四：T（n）=0.5n^2+0.5n，最高阶项为0.5n^2，省去前面系数0.5，所以转化之后的时间复杂度为O（n^2）。
但在实际的算法中，时间复杂度远不止这4种类型，这里只是列出一些比较常见的例子，除了这些还有O(nlongn)、O(n^3)、O(mn)、O(2^n)、O(n!)……这些在以后的文章中都会一一说到。
三、空间复杂度
什么是空间复杂度？
这里由一道题的两种方法来引出空间结构：
给出n个整数，其中有两个整数是重复的，试问如何找出这两个重复的整数？
方法一：双重循环
直接遍历整个数列，每遍历到一个新的整数就开始回顾之前遍历过的整数，看是否有相等的整数，用代码可以表示为：
public class TestDemo {
public static void main(String[] args) {
int[] array=new int[]{3,1,2,5,4,9,7,2};
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < i; j++) {
if(array[j]==array[i]){
System.out.println(array[j]);
break;
}
}
}
}
}这样的双重循环虽然也是可以找到那个重复的整数，但是其使用了两次循环，显然并不是最优的解法。由前面介绍的时间复杂度可以看出该段代码的时间复杂度是O（n^2）。
方法二：“字典”法
由上面的双重循环代码中时间复杂度太大，我们就会想出一种更为高效的算法 ——“字典”法。当遍历整个数列的时候，每遍历一个整数，就把这个整数给存起来，就类似与将其放在一个字典中一样，下一次再对其进行查找，这样就不用使用双重循环了，用代码可以表示为：
public class TestDemo {
public static void main(String[] args) {
int[] array=new int[]{3,1,2,5,4,9,7,2};
int[] brrby=new int[10];
for (int i = 0; i < array.length; i++) {
brrby[array[i]]+=1;
if(brrby[array[i]]==2){
System.out.println(brrby[array[i]]);
break;
}
}
}
}这样，由于读写“字典”本身的时间复杂度是O（1），所以整个算法的时间复杂度是O（n），跟上面的双重循环相比，效率是提高了不少。但是这个“字典”是一种特殊的数据结构——散列表。这样的数据结构相比上面的双重循环来说，需要开辟一定的内存空间来存储有用的数据信息，这样就照成了空间复杂度的增加。
由上面的两个例子可以知道空间复杂度是上面东西，实际上说白了就是和时间复杂度类似的（同样是使用大O表示法），只是空间复杂度是对一个算法再运行过程中临时占用存储空间大小的量度。
程序占用空间大小的计算公式记作S(n)=O(f(n))，其中n为问题的规模，f(n)是算法所占存储空间的函数。
空间复杂度的计算
常见的空间复杂度主要有下面几种情况：
1.常量空间
public class TestDemo {
public static void main(String[] args) {
fun1(5);
}
public static void fun1(int n){
int a=10;
System.out.println(a);
}
}当算法的存储空间大小固定，且和输入规模没有直接的关系的时候，空间复杂度为O（1）。
2.线性空间
public class TestDemo {
public static void main(String[] args) {
fun2(5);
}
public static void fun2(int n) {
int[] array=new int[n];
array[5]=10;
System.out.println(array);
}
}当算法分配的空间是一个线性的集合（比如数组），并且集合大小和输入规模n成正比的时候，空间复杂度为O（n）。
3.二维空间
public class TestDemo {
public static void main(String[] args) {
fun3(5);
}
public static void fun3(int n) {
int[][] array=new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
array[i][j]=10;
}
}
}
}当算法分配的空间是一个二维空间集合，并且集合的长度和宽度都与输入规模n成正比的时候，空间复杂度为O（n^2）。
4.递归空间
public class TestDemo {
public static void main(String[] args) {
fun4(5);
}
public static void fun4(int n) {
if(n<=1){
return;
}
fun4(n-1);
}
}像上面代码中这种递归类型来说，是一种比较特殊的场景。虽然递归代码中没有显示出声明变量或集合，但是再计算机中，执行该程序的时候，会专门分配一块内存，用来存储“方法调用栈”。当进入一个新方法时，执行 入栈操作，把调用的方法和参数信息压到栈中；当方法返回时，执行 出栈操作，把调用的方法和参数信息从栈中弹出。
执行递归操作所需的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，则空间复杂度就是O（n）。
四、时间和空间的取舍
在计算机中，时间和空间两者是互相矛盾的，当得到一些空间的时候必定会失去一部分时间，当节省了一部分时间的时候就必定会失去一些空间。就像上面说到的双重循环法和“字典”法，双重循环法就是典型的牺牲时间来换取空间；而“字典”法就是典型的牺牲空间来换取时间。俗话说：有得有失，有失有得。但是在大多数的情况下，都会宁可多分配一些内存空间，也要提高程序的运行速度，所以，时间复杂度更为重要一些。