| 2020-04-10 test test 1 \[f(x)=a_1x^2+b\] \[\left \lbrace \sum_{i=0}^n i^3 = \frac{(n^2+n)(n+6)}{9} \right \rbrace\]
| 2020-04-08 千禧问题：P = NP ？ 千禧问题 今天我们要说一个计算机领域里的一个超级难题，P 是否等于 NP。在 2000 年 5 月的时候 Clay Institute 将这个问题列为了数学里的七大千禧问题之一，如果有人能证明出 P = NP 或 P ≠ NP，就会获得该机构整整 100 万美元的奖金。并且一旦证明出 P = NP 将会改变现在人类所有的知识体系，这个我们在后面的部分再详细说。怎么样，是不是有了想证明它的冲动呢？接下来我们就来看看这个问题到底在讲什么吧。 千禧问题 P 问题与 NP 问题 ...
| 2020-04-01 分支限界 介绍 前面我们学习了回溯法，它的主要思想是不停地探索我们的状态空间，如果遇到不满足条件的解就停止探索，然后回溯到上一个状态，再探索其他的状态，直到得到问题的解。 回溯的方法的确是一种可行的办法，但是它只能求解问题的类型却是有限的。像 n-皇后，集合问题它都是可以解决的，但对于优化问题它却束手无策了。回溯的过程只会发生在探索过程中不满足限制条件时发生，用回溯法求解的问题一般都有多个解，但对于最优问题（分配问题、背包问题等）来讲，满足限制条件的解有很多，我们要做的是从所有满足条件 ...
| 2020-03-23 回溯 写在前面 从这一节开始，我们就要讨论一些更复杂的算法问题了。对于之前的内容，如果还有不是特别明白的小伙伴呢，建议你们先理解前面所学的内容，再来看这一部分。因为这一整章的内容都是打了星号的，属于算法的较为高阶的部分，所以你也可以选择直接跳过这一部分内容。 引入 我们知道，组合问题的求解是最耗时也是最难解决的问题之一，如果用暴力求解的方式来解决它，我们需要将这个问题的所有组合情况，也就是穷举出所有的子集，然后从子集中选择满足条件者。例如，从集合 {1, 2, 5, 6} 中选出元 ...
| 2020-03-18 2-3 树 介绍 无论是 AVL 树还是红黑树，它们都有个共同的特点：每个节点最多只能存放一个值，并且最多只有两个子节点。我们知道，AVL 树和红黑树的查找效率接近于 Θ(log n)，这得益于我们将树的结构做了调整，使得树的高度尽可能的减小，来达到平均搜索的次数减少。因此，从这一点可以启发我们，要想使查找效率高，我们就要尽可能的减小树的高度，于是就有了多路查找的树，就好比树根有多条分叉一样，这里我们只说最经典的 2-3 树。 树根 两种节点 2-3 树从字面上很难理解它要传达出的意 ...
| 2020-03-13 哈弗曼树 字符编码 我们知道，计算机只能读懂由 0 和 1 构成的二进制编码。因此，我们每天看到的汉字或英文字符都会被编码成二进制的形式，如果你熟悉一些常用的编码方式，你会发现无论是ASCII码还是Unicode，每个字符都占用都是等长的的编码位，也就是说，无论是 A, B, C, D 还是 + - × ÷，它们都是有 m 个 0 和 1 的二进制来编码。 编码 但这样的编码会出现一些问题，我们先假设 A, B, C, D, E 对应的编码分别为 000, 001, 010, 01 ...
| 2020-03-09 迪克斯特拉算法 背景 当我们在家中享受着互联网给我们带来的便利时，你是否想过你的电脑或手机是怎样把这些请求发送到服务器端，而服务器端又怎样把数据包发送到我们的设备的呢？要知道，互联网是由数以亿计的计算机相互连接而成，我们在发送一个数据包时，网络中的路由器会充当接收并转发的中转站，并且这些路由器总是会将数据发给最近的其他路由器，在网络中也就是路由器之间的延迟最小 网络 在弗洛伊德算法那一节里，我们提到过什么是最短路径问题，以及它的两种类别。假设在一个网络中有 10000 台计算机，它们彼此 ...
| 2020-03-07 克鲁斯卡尔算法 另一种猜想 上一节我们学习了如何用普林姆算法来解决最小生成树的问题。简单回顾一下，算法一开始从节点集合 V 中任选一个节点作为起始节点，然后选择与之相邻的最小权重的边，如果这条边对应的下一个节点没有被访问过，那么就将这条边作为最小生成树的一部分；否则就看权重第二小的边是否满足要求。上述过程重复执行 |V| - 1 次，我们就可以得到一个图的最小生成树。 普林姆 我们看到，普林姆算法是基于现成的图结构来得到最小生成树的。其实，我们还可以这样想：将图中的所有边全部拆开，使节点 ...
| 2020-03-05 普林姆算法 贪心算法 前面我们讲到的动态规划一般都是解决的最优问题，通常情况下我们先将原问题拆分成数个子问题，然后找出这些子问题之间的关系，即怎样从规模为 n - 1 的子问题的解中推出规模为 n 的子问题的解（F(n-1) --> F(n)），最后从最小子问题入手，用迭代的方式求出原问题的解。这样虽然每次都能求出最优解，并且这里的最优是全局最优，但是动态规划的方法过于复杂，难以理解，需要额外的内存空间来储存子问题的解。在一些只需要近似最优解的场景中，动态规划未免显得有点头重脚轻了 ...
| 2020-03-01 弗洛伊德算法 图的最短路径 生活中，当我们在使用高德地图导航的时候，系统总是为我们选择最近的路。我们知道从一个地方到另一个地方可能有很多条路可以选择，而高德地图是怎样做到为我们选择更近的路呢？这就要用到图的最短路径了。 地图 在计算机里，我们用有权图来表示城市的路网，其中每个节点代表一个地点，每条边代表从一个地方到另一个地方的距离，数据结构我们使用邻接矩阵的形式。 计算最短路径分成两种情况，一种是一次计算所有点对的最短路径，就是下面我们要讲到的弗洛伊德算法；另一种是单源最短路径，也就是 ...
