yunnight HomeArchivesTagsCategories
《算法图解》笔记
| 算法

前言

　　《算法图解》这本书真的非常好懂，它结合图画，对算法基础知识讲得很透，把“每一步要怎么做”和“为什么这样做”都交代了。这些知识以前在学校也学习过，但那时候只记住算法每一步怎么做，时间复杂度也是硬背的，根本没去理解背后的原因。这样的后果就是学完就忘。这本书就很适合我这种对算法稍微懂点但又不是很懂的人，它帮我把以前的疑惑都解开了。但它有个局限性就是，只讲基础，对稍微难点的内容都是一笔带过，只能靠个人去学，真正的入门书。
　　因为作者就像聊天似的教算法，图画也多，所以这本书的知识点比较散，这篇博客就是将我从这本书学到的知识点记录下来。

大O表示法

  • 大O表示法体现的是随着元素数量n的增多，操作次数的增长趋势。如O(logn)（二分查找）的增长趋势明显比0(n)（简单查找）要慢得多，因此可以说二分查找比简单查找更好
  • 大O表示法一般是该算法在最糟情况下的速度，但算法也有平均情况（也是最优情况）下的速度。如快速排序最糟O(n^2)，平均O(nlogn)
  • 大O表示法不含常量的原因：当元素数量很多时，常量对速度的影响可忽略不计
  • O(1)表示常量时间，含义是无论元素数量多少，所需时间都一样

注：

  1. 这本书里只讨论时间复杂度，没讲空间复杂度
  2. logn就是log2n，即2的幂

数组和链表

  • 在内存方面：数组元素的内存地址是相邻的，链表元素的内存地址不用相邻，链表的每个元素中都会存放下一个元素的内存地址
  • 在查找方面：链表只能顺序查找，而数组可以随机访问到任一元素，因此说数组的查找效率更好
  • 在插入和删除方面：链表的插入和删除只是改变某个元素存储的下一个元素的地址，数组的插入要重新分配内存，删除时要把后面的元素往前移
  • 链表的插入和删除都是O(1)，这不包括“查找插入/删除位置”的时间

递归

  • 递归没有什么性能优势，只是让代码更清晰。可以用递归实现的也能用循环实现
  • 每个递归都包含两个条件：递归条件–让函数调用自己的条件，基线条件–函数return的条件（即不再递归的条件）
  • 每次递归调用都会加入到调用栈，占用内存，执行完就会从调用栈弹出

尾递归

　　在调用栈过高的情况下，可以写成尾递归的形式。尾递归就是手动把本次调用的计算结果作为递归函数的参数，这样在return时就直接return递归，而不是还要先处理递归结果再return。
　　下面以阶乘函数为例，展示递归和尾递归的不同写法：

普通递归：

1
2
3
4
5
6
public int fac(int n) {
	if (n <= 1)
		return 1;
	else 
		return n * fac(n - 1);
}

尾递归：

1
2
3
4
5
6
public int fac2(int n, int t) { //第一次调用时t=1
	if (n <= 1)
		return t;
	else
		return fac2(n - 1, n * t);
}

　　写成尾递归后，若编译器会自动帮你把尾递归代码优化就会很好用（jvm不会），否则需要你手动把尾递归代码优化了才会有节省栈内存的效果。尾递归可以优化的原因：每次递归都计算出了一个结果，上一次递归的结果就没必要保留，可以释放内存。

分而治之（D&C）

  • 分而治之是一种递归式的问题解决方法。思路是缩小问题范围，思考解决小问题的方法，能解决小问题的方法也适用于大问题。欧几里得算法就是这个思路

    两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

  • 工作过程：a.找出基线条件，这个条件必须尽可能简单；b.缩小问题的规模，使其符合基线条件

  • 要处理的对象是数组时，基线条件一般是数组为空或只含一个元素

举例：求数组[1,2,3,4,5]的总和，基线条件为：当数组只有一个元素时数组总和就等于这个元素。做法就是：不断挑出一个元素，使数组规模变小，求(挑出的元素+数组剩余元素总和)的值。

1
2
3
4
5
6
7
8
9
10
11
12
public int sum(int[] arr) {
	int len = arr.length;
	if (len == 1) {
		return arr[0];
	} else {
		int[] aArr = new int[len - 1];
		for (int i = 1; i < len; i++) {
			aArr[i - 1] = arr[i];
		}
		return arr[0] + sum(aArr);
	}
}

上面代码只是为了说明“分而治之”的思想，一般情况下求数组总和还用不到递归。

注：这本书说的“分而治之”的概念是其他一些教材说的“减而治之”。一些人把“减而治之”看作是“分而治之”的一种特殊情况，作者这样写也没错。

散列表

  • 由数组和散列函数组成，通过散列函数将要存储的值计算成数组索引，值就放在索引处
  • 良好的散列函数会尽量覆盖数组的每个位置，即每个值都放在不同位置

二分查找

  • 只适用于有序数列
  • 运行时间为O(logn)，就是把一串数字对半分，直到只剩一个数字的次数
  • 操作过程也运用了递归思想。基线条件：数组中间元素与目标相同；递归条件：当中间的元素不对，对一半数组继续二分查找

循环式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearch(int[] n, int target) {
	int high = n.length - 1;
	int low = 0;
	while (low <= high) {
		int mid = (high + low) / 2;
		int i = n[mid];
		if (i == target)
			return mid;
		else if (i < target) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return 0;
}

递归式：

1
2
3
4
5
6
7
8
9
10
11
12
public int binarySearch2(int[] n, int target, int high, int low) {
	int mid = (high + low) / 2;
	int num = n[mid];
	if (num == target)
		return mid;
	else if (num < target) {
		low = mid + 1;
	} else {
		high = mid - 1;
	}
	return binarySearch2(n, target, high, low);
}

注意：在实际使用中，当数组元素值都很大时，上面求中值的算式int mid = (high + low) / 2会有int溢出的可能，把它替换为low + (high - low) / 2会更好。

选择排序

  • 重复从数组中挑出最大或最小的元素放入新数组，直到原数组没有元素了
  • 运行时间为0(n^2)，从n个元素中挑最大或最小（相当于把每个元素检查一遍），要挑n次，所以是n*n

快速排序

  • 过程：选出一个基准值pivot，比基准值小的数作为一个子数组a1，比基准值大的数作为子数组a2，qsort(a1) + pivot + qsort(a2)就是结果
  • 平均情况下运行时间是O(nlogn)，即随机选取基准值，子数组a1和a2的元素个数基本是原数组的一半，调用栈高为logn，每一层栈要处理的元素数是n，所以是n*logn
  • 最糟情况下运行时间是O(n^2)，即选取的基准值是最大或最小数，子数组a1和a2中总有一个为空，此时调用栈高为n，每一层栈要处理的元素数是n，所以是n*n

附：合并排序（Merge Sort）
　　合并排序就是把数组对半分，再递归把子数组对半分直到只有一个元素（栈高度logn），每一次对半分好后通过比较两个子数组的元素合并为一个有序数组（操作元素数n），合并排序的平均和最糟情况都是0(nlogn)

图算法

  • 图的结构包含：节点(V)和边(E)

  • 树是一种特殊的图：不存在子节点往父节点指的边

  • 节点之间有严格的先后顺序的图，叫拓扑排序

  • 非加权图找最短路径：广度优先搜索（下节详细说明）

  • 加权图（不含负权边）找最短路径（即权重之和最小）：狄克斯特拉算法
    狄克斯特拉算法的思路：

    1. 从所在节点的相邻节点中，找出“最便宜”的节点，即到达此相邻节点的权重最小
    2. 到达上一步所述的“最便宜”的节点后，更新从起点到达该“最便宜”节点的相邻节点的权重和
    3. 重复这个过程，直到对图中的每个节点都这样做了
    4. 计算最终路径的权重之和

  • 加权图（含负权边）找最短路径（即权重之和最小）：贝尔曼-福德算法

  • 狄克斯特拉算法不适合用在带环的图

广度优先搜索

广度优先搜索就是，从起点开始，判断走一步能到达的顶点中有没有终点，若没有，就判断走两步能到达的顶点中有没有终点。。。找到终点后，走的步数就是最短路径。

广度优先搜索可以解决2个问题：

  1. 是否能到达终点
  2. 到达终点的最短路径

专门用于找非加权图的最短路径。

运行时间

广度优先搜索的运行时间：O(V+E)。V是图的节点数，E是边数。

实现思路

  1. 用一个散列表存图的节点和边，key为每个节点，value为这个节点的相邻节点（邻居）列表
  2. 准备一个空队列
  3. 从第一个节点开始，把该节点的邻居加入空队列
  4. 遍历队列中的每个节点，判断它们是不是终点，如果是，则返回最短步数；如果不是，把该节点的邻居加入队列（尾插），并删除该节点（头删）
  5. 用一个列表保存被判断过的节点，避免同一个节点被重复判断

广度优先和深度优先

NP完全问题（NPC）

  • 无法快速找到最优解的就是NP完全问题

  • 集合覆盖问题 和 旅行商问题 就是典型的NP完全问题。背包问题属于集合覆盖问题。

  • 解决NP完全问题，最好使用近似算法。贪婪算法就是近似算法的一种，无法得到最优解，但也接近最优解
    贪婪算法，就是在限制的条件内，每一步都采取最优的做法。如背包问题中，每次都放入价值最高的物品，直到放不下为止

  • 动态规划可以帮助找到NP完全问题的最优解

    • 可以使用动态规划的条件有：

      • 问题可以分解为互相独立的子问题。如背包问题中，放手机和放电脑彼此是独立的，谁先放都不会影响到另一个的价值
      • 使用动态规划，问题的对象只有两种状态，有和没有，不能考虑“有一部分”这样的情况。如背包问题中，放一袋大米，只能考虑放整袋，不能考虑把米袋拆了只拿一部分

    • 动态规划的步骤

      1. 绘制网格
      2. 决定网格的坐标轴代表什么。因为每个网格都代表一个子问题，所以要考虑怎么划分子问题。如对比两个字符串中相同字母的个数（求最长公共子序列问题），子问题就是一个字母一个字母的比较，所以坐标轴就是两个字符串
      3. 决定网格内的值代表什么。一般就是要优化的值。如求最长公共子序列问题，网格内的值就是相同字母的个数
      4. 决定网格内的值的计算公式。这个要通过经验和尝试来决定
  • NP完全问题的特征：
    1. 元素数越多，算出最优解的时间越长
    2. 不能使用“分而治之”，必须考虑所有情况的问题
    3. 可以转化为集合覆盖问题或旅行商问题

附：数学建模中其实有四类问题：P问题、NP问题、NP完全问题（NPC）、NP难问题（NPH），概念涉及到多项式，很复杂，这里不讨论。