Computational Thinking ** Decomposition: 把数据、过程或问题分解成更小的、易于管理的部分。
Pattern Recognition: 观察数据的模式、趋势和规律。
Abstraction: 识别模式形成背后的一般原理。
Algorithm Design: 为解决某一类问题撰写一系列详细步骤。

什么是算法（What）

算法就是计算或者解决问题的步骤。我们可以把它想象成食谱。要想做出特定的料理，就要遵循食谱上的步骤；同理，要想用计算机解决特定的问题，就要遵循算法。

需要注意的是：同一个问题，可以用很多不同的算法来解决；同一个算法，可以用很多不同的编程语言来实现；同一个编程语言，可以用很多不同的数据结构来编写。

拿食谱来做类比，如果做一道【西红柿炒鸡蛋】是我们的具体问题，那么不同的厨师会有不同步骤（做出来的味道当然也不尽相同）；即使同样的步骤，下料的时机、多少以及火候等也会不一样；即使用料，火候都一样，那么采用的食材（打鸡蛋的方式，西虹市刀工等）也可能不一样。

即使如此，我们都解决了同一个问题（做一道菜）。只不过口味，营养丰富程度及所需要消耗的时间各有不同。

为什么需要算法（Why）

计算机擅长高速执行一些基本命令，但无法执行复杂的命令。此处的“基本命令”指的是“做加法”或者“在指定的内存地址上保存数据”等。

计算机是以这些基本命令的组合为基础运行的，面对复杂的操作，也是通过搭配组合这些基本命令来应对的。“对 n 个数字进行排序”这类问题对计算机来说就是复杂的操作。如何设计算法来解决这个排序问题，也就等同于构思如何搭配组合计算机可以执行的那些基本命令来实现这个操作。

如何选择算法（How）

能解决排序问题的算法不止选择排序这一个。那么，当有多个算法都可以解决同一个问题时，我们该如何选择呢？在算法的评判上，考量的标准也各有不同。

算法经典 - 排序

问题：以随意排列的整数（一共n个）为输入，把它们按从小到大的顺序重新排列后输出

步骤1：从输入的数字中找出最小的数字，再将它和最左边的数字交换位置（1 <—> 7）

步骤2：固定最左边的 k 个数字，在剩余的 n-k 个数字中重复 步骤1

算法复杂度 O(n)

简单的算法对人来说易于理解，也容易被写成程序，而在运行过程中不需要耗费太多空间资源的算法，就十分适用于内存小的计算机。

不过现代计算机，存储空间足够大的情况下，一般来说我们最为重视的是算法的运行时间，即从输入数据到输出结果这个过程所花费的时间。

复杂度数学表述

用于描述函数渐近行为的数学符号，称为渐进符号：

• ο 表示上界，小于的意思。 < n
• Ο 表示上界，小于等于的意思。 ≤ n
• Ω 表示下界，大于等于的意思。 ≥ n
• ω 表示下界，大于的意思。 > n
• Θ 表示上界于下界的结合，等于的意思。 = n

复杂度图表

数据结构的复杂度

排序算法的复杂度

| Algorithm | | Complexity | |

| —- | —- | —- | —- | | | Time (agv.) | Space (worst) | | Quicksort | 快速排序 | Θ(nlog(n)) | O(log(n)) | | Mergesort | 归并排序 | | O(n) | | Timsort | 优化归并排序 | | | | Heapsort | 堆排序 | | O(1) | | Bubble Sort | 冒泡排序 | Θ(n^2) | | | Insertion Sort | 插入排序 | | | | Selection Sort | 选择排序 | | | | Tree Sort | 树排序 | Θ(nlog(n)) | O(n) | | Shell Sort | 希尔排序 | Θ(n(log(n))^2) | O(1) | | Bucket Sort | 桶排序 | Θ(n+k) | O(n) | | Radix Sort | 基数排序 | | O(n+k) | | Counting Sort | 计数排序 | | O(k) | | Cubesort | 立方排序 | Θ(n*log(n)) | O(n) |

Interactive Visualization

Graph

• single-source shortest paths

Sorting

• bubble, selection, insertion, merge, quick, random quick, counting, radix

一、Algorithms Thinking

1. Greedy
2. Dynamic Programming
3. Backtracking
4. Divide & Conquer

Describing Algorithms

A complete description of any algorithm has four components:

• What: A precise specification of the problem that the algorithm solves.
• How: A precise description of the algorithm itself.
• Why: A proof that the algorithm solves the problem it is supposed to solve.
• How fast: An analysis of the running time of the algorithm.

Use Algorithms in Data Structure

• Search − Algorithm to search an item in a data structure.
• Sort − Algorithm to sort items in a certain order.
• Insert − Algorithm to insert item in a data structure.
• Update − Algorithm to update an existing item in a data structure.
• Delete − Algorithm to delete an existing item from a data structure.

二、排序

排序就是将输入的数字按照从小到大（或者从大到小）的顺序进行排列。

2.1 冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。

2.2 选择排序

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找。

2.3 插入排序

插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

2.4 堆排序

堆排序的特点是利用了数据结构中的堆。

2.5 归并排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时(也就是每个子序列中只有一个数据时)，就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

2.6 快速排序

速排序算法首先会在序列中随机选择一个基准值(pivot)，然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式：

[比基准值小的数] 基准值 [比基准值大的 ]

接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据 进行排序时同样也会使用快速排序。

三、数组的查找

3.1 线性查找

线性查找是一种在数组中查找数据的算法。与二分查找不同，即便数据没有按顺序存储，也可以应用线性查找。线性查找的操作很简单，只要在数组中从头开始依次往下查找即可。虽然存储的数据类型没有限制。

3.2 二分查找

和线性查找不同，它只能查找已经排好序的数据。二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。因此，比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据，或得出目标数据不存在的结论。

注：二分查找必须建立在数据已经排好序的基础上才能使用，因此添加数据时必须加到合适的位置，这就需要额外耗费维护数组的时间。而使用线性查找时，数组中的数据可以是无序的，因此添加数据时也无须顾虑位置，直接把它加在末尾即可，不需要耗费时间。

四、图的搜索

4.1 广度优先

广度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点(即起点)，此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点(即终点)。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。

搜索顺序为：A、B、C、D、E、F、H…

4.2 深度优先

深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索直到到达指定顶点(终点)。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

搜索顺序为：A、B、E、K、F、C、H

深度优先搜索的特征为沿着一条路径不断往下，进行深度搜索。虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，那就是选择哪一个候补顶点作为下一个顶点的基准不同：

• 广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索
• 而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。

4.3 Bellman-Ford 算法

贝尔曼-福特(Bellman-Ford)算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。

4.4 Dijkstra 算法

与前面提到的贝尔曼-福特算法类似，狄克斯特拉(Dijkstra)算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。

4.5 A* (A-Star)算法

A(A-Star)算法也是一一种在图中求解最短路径问题的算法，由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A就会预先估算一个值，并利用这个值来省去一些无用的计算。

五、数据安全 TODO: 中间人

传输数据时的四个问题：

• 窃听：A 向 B 发送的消息可能会在传输途中被 X 偷看。
• 假冒：A 以为向 B 发送了消息，然而 B 有可能是 X 冒充的；反过来，B 以为从 A 那里收到了消息，然而 A 也有可能是 X 冒充的。
• 篡改：即便 B 确实收到了 A 发送的消息，但也有可能该消息的内容在途中就被 X 更改了。
• 事后否认：B 从 A 那里收到了消息，但作为消息发送者的 A 可能对 B 抱有恶意，并在事后声称“这不是我发送的消息”

->

解决这些问题的安全技术：

• 加密
• 消息认证码
• 数字签名 -> 数字证书

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。其特征如下：

1. 输出的哈希值数据长度不变。
2. 如果输入的数据相同，那么输出的哈希值也必定相同。
3. 即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似。
4. 即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”。
5. 不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不同。
6. 求哈希值的计算相对容易。

哈希函数：

• MD5 (Message Digest Algorithm 5)
• SHA-1 (Secure Hash Algorithm)
• SHA-2
• …

加密技术

将数据变成第三者的计算机无法理解的形式，然后再将其恢复成原本数据的一系列操作。

加密数据的方法可以分为两种：

• 加密和解密都使用相同密钥的“共享密钥加密” - 对称加密
  • 凯撒密码
  • AES(Advanced Encryption Standard)
  • DES(Data Encryption Standard)
  • 动态口令等
• 分别使用不同密钥的“公开密钥加密” - 非对称加密
  • 加密用的密钥叫作“公开密钥”
  • 解密用的叫作“私有密钥”。
  • 由接收方 B 来生成公开密钥 P(public key) 和私有密钥 S(secret key)
  • RAS(Rivest、Shamir、Adleman ) 算法、椭圆曲线加密算法等
    • 可以使用某个数值对数据进行加密(计算)。
    • 使用另一个数值对加密数据进行计算就可以让数据恢复原样。
    • 无法从一种密钥推算出另一种密钥。

消息认证码

由密钥和密文生成的值就是消息认证码，简称为 MAC(Message Authentication Code)

• 可以把 MAC 想象成是由密钥和密文组成的字符串的“哈希值”。
• 计算 MAC 的算法有 HMAC 1、OMAC 2、CMAC 3等。目前，HMAC 的应用最为广泛。

加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。如果原本的消息是很长的句子，那么它被篡改后意思会变得很奇怪，所以接收者有可能会发现它是被篡改过的。

但是，如果原本的消息就是商品编号等无法被人们直接理解的内容，那么解密后接收者便很难判断它是否被篡改。由于密码本身无法告诉人们消息是否被篡改，所以就需要使用消息验证码来检测。

数字签名

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。

数字证书

“公开密钥加密”和“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。不过，如果使用本节讲解的数字证书，就能保证公开密钥的正确性。

六、数据挖掘

聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。1 个组就叫作 1 个 “簇”。下面的示例中每个点都代表 1 个数据，在平面上位置较为相近、被圈起来的点就代表一类相似的数据。也就是说，这些数据被分为了 3 个簇。

如何定义“相似”

根据数据类型不同，定义该数据是否“相似”的标准也不同。具体来说，就是要对两个数据之间的“差距”进行定义。

聚类的方法

可以设定各种各样的条件，比如想把数据分为 10 个簇，或者想把 1 个簇内的数据定在 30~50 人之间，再或者想把簇内数据间的最大距离设为 10，等等。而设定什么样的条件取决于进行聚类的目的。

k-means 算法

聚类算法中的一种，可以根据事先给定的簇的数量进行聚类。步骤：

1. 准备好需要聚类的数据，然后决定簇的数量 n。
2. 确定数据间的”差距“算法。
3. 随机选择 n 个点作为簇的中心点。
4. 计算各个数据分别和 n 个中心点中的哪一个点距离最近。
5. 将数据分到相应的簇中。这样，n 个簇的聚类就完成了。
6. 计算各个簇中数据的重心，然后将簇的中心点移动到这个位置。
7. 重新计算距离最近的簇的中心点，并将数据分到相应的簇中。
8. 重复执行 6 和 7 这两步操作，直到中心点不再发生变化为止。
9. 即使继续重复操作，中心点也不会再发生变化，操作到此结束，聚类也就完成了。

由于 k-means 算法需要事先确定好簇的数量，所以设定的数量如果不合理，运行的结果就可能会不符合我们的需求。如果对簇的数量没有明确要求，那么我们可以事先对数据进行分析，推算出一个合适的数量，或者不断改变簇的数量来试验 k-means 算法。

即使簇的数量相同，只要随机设置的中心点最初的位置不同，聚类的结果也会产生变化。因此，我们可以通过改变随机设定的中心点位置来不断尝试 k-means 算法，再从中选择最合适的聚类结果。

七、经典算法

欧几里得算法

又称辗转相除法，用于计算两个数的最大公约数，被称为世界上最古老的算法。

求数字 1112 和 695 的最大公约数。传统做法：

欧几里得算法：

素性测试

判断一个自然数是否为素数的测试。素数(prime number)就是只能被 1 和其自身整除，且大于 1 的自然数。素数从小到大有 2、3、5、7、11、13……目前在加密技术中被广泛应用的 RSA 算法就会用到大素数，因此“素性测试”在该算法中起到了重要的作用。

费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。

实际上不只是 5，对于任意素数 p，上面的公式都是成立的。这就是“费马小定理”。根据是否满足费马小定理来判断一个数是否为素数的方法就是“费马测试”。

确认 n 和余数一致的次数越多，需要判断的数确实为素数的可能性就越大。但是，如果每一个小于 p 的数都要去计算，就会非常耗费时间。实际上，如果确认了几组 n 和 余数之后就能判断该数是素数的可能性非常高，那么大致就可以判定该数是素数了。

在 RSA 算法中，用于素性测试的是根据费马测试改进而来的“米勒 - 拉宾 (Miller-Rabin)素性测试”。用这个方法重复进行测试后，当数不是素数的概率小于 0.5^80 时，就可以大致判断该数为素数。

即使所有 n 都满足条件，p 也有可能不是素数。因为在极低概率下会出现所有 n 都满足条件的合数(非素数的自然数)。这样的合数就叫作“卡迈克尔数”(Carmichael numbers)，也叫“绝对伪素数”。

网页排名

站在互联网空间的视角，来观察某位互联网用户的网页浏览行为过程（随机游走模型 random walk mode），就会觉得浏览网页的人只是在不断重复着“在有链接指向的页面之间移动几次之后，远程跳转到了完全不相关的网页”这一过程。

以前的搜索引擎都是以关键词和网页内容的关联性来决定搜索结果的排列顺序，但这种方法没有考虑网页内是否含有有效内容，因此搜索精度较低。

Google 公司提供了使用网页排名算法的搜索引擎，然后凭借其强大的性能成为了世界知名企业。当然，如今决定 Google 搜索结果排序的已不仅仅是网页排名这一个算法了。

汉诺塔

汉诺塔是一种移动圆盘的游戏，同时也是一个简单易懂的递归算法应用示例。

移动条件：

1. 1 次只能移动 1 个圆盘。
2. 不能把大的圆盘放在小的圆盘上。

步骤：

1. 想移动 n 个圆盘，只需要按照移动 n - 1 个圆盘时的方法移动即可。
2. 而要移动 n - 1 个圆盘，就需要按照移动 n - 2 个圆盘时的方法移动。
3. 这样追溯下去，最终就会回到移动 1 个圆盘时的操作方法上。

像这样，在算法描述中调用算法自身的方法就叫作“递归”。

hanoi(n, src, dst, tmp):
    if n > 0:
        hanoi(n-1, src, tmp, dst)
        move disk n from src to dst
        hanoi(n-1, tmp, dst, src)

八、应用

相遇问题