算法讲义 | Tdotd’s Blog

type

date

status

slug

summary

什么是算法？

算法，顾名思义，就是算的方法，是为完成一个确定目标而进行的一系列操作的集合，这种方法反应在程序上就是一组程序的运行。

作为一名程序员，我们的本职工作可能不在于开发新的算法，而是将已经掌握的算法映射到某些语言的程序当中，因此，我们所遇到的难点就是实现这种抽象操作到具体代码的映射，这也是我们需要去学习的。同时，我们知道，算法的输入和输出，以及算法在运行过程中的基础，就是数据，如果将这些数据输入到程序当中，它也必然存在着一定的组织结构，即数据结构，不同的数据结构能产生出不同的算法。除此之外，还要考虑程序的运行结构。

程序的两种运行结构

迭代

迭代(iteration)，是一种重复执行某个人物的控制结构。在迭代中，程序会在满足一定条件下重复执行某段代码，直到这个条件不再满足，这种结构一般由程序中的循环结构来实现。

其基本思想是为了解决问题而将某一特定的操作序列多做几次，以得到最终结果。（自下而上）

递归

递归(recursion)，是一种十分重要的算法策略，其通过函数调用自身来解决问题。它主要包含两个阶段：

递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”；

归：触发“终止条件”后，程序从最深处的递归函数开始逐层返回，汇聚每一层的结果。

其基本思想是，将原问题分解为具有相同形式的子问题，持续分下去，再将子结果汇总，得到最终结果。（自上而下）

尾递归

尾递归的基本原理是，通过巧妙的设计函数传参的方式，使得递归调用自身成为函数返回前的最后一个操作（无需对结果进行其他处理，即最终结果就存在于递归调用返回结果当中，与当前函数的栈帧环境无关）。

复杂度分析

我们利用对一个算法运行时间随输入数据的规模增大的增长趋势的粗略地估计来代替对实际算法运行过程的准确测量，来简化算法复杂度的分析。

复杂度分析概念

设一个算法的操作数量为T(n)，O(f(n))是T(n)的渐进上界，可以用作该算法的时间复杂度。

对O(f(n))的数学定义如下：

若存在正实数c和实数n0，使得对于所有的n > n0，均有T(n) <= c * f(n)，则可认为f(n)给出了T(n)的一个渐进上界，记为T(n) = O(f(n))。

例如，若干T(n) = 3 + 2n，则其线性阶的时间复杂度为O(n)，即f(n) = n；

数据结构

线性数据结构

所谓线性数据结构是指数据元素在逻辑上来讲是线性排列的。

数组：在物理结构上，顺序排列的一系列数据元素。由于它是连续的结构，一旦初始化后，其大小不可改变，是一种静态的数据结构；

链表：在物理结构上，通过一个指针，实现在虚拟内存中的分散存储。其元素个数可以动态改变，是一种动态数据结构；

复杂数据结构

复杂数据结构是利用线性数据结构组合而来的。

树状；

图状；

等等。

数组

在物理结构上，数组是一段连续存放的内存空间，其一旦被初始化，其空间位置就是固定的，其大小也是不可变的，因此就导致了数组具有了如下特点：

空间利用率高：由于是连续存储，因此不需要额外的空间来记录其他信息；

可以随机访问：这也是连续存储导致的；

对元素的访问速度快：空间局部性；

插入与删除元素的效率较低；

扩容较为低效：长度不可变，需要重新开辟新的内存空间，并进行复制；

如果存储的元素较少，可能导致空间资源的浪费；

链表

与数组不同，链表通过在数据元素中添加一个指针域，用于存放其下一个节点的地址，来实现了物理结构上的分散存储。

由于相比于数组，添加了一个指针域，链表在对元素的插入与删除上要比数组快速很多，而又由于其分散存储的物理结构，其在访问元素上又产生了不可避免的时间浪费。

哈希表

所谓哈希表，其实就是一个具有一定容量的字典，其中缓存了一些信息，我们在需要这些信息时，可以通过一个key值，来得到对应的value值。

二叉树

二叉树(binary tree)是所有树的基础结构，它所承载的是一种一分为二的分治逻辑。

究其本质，树也就是链表的一种变体，一种升级，如果所有的节点都只包含左子树或右子树，那么其也就退化成了链表。

二叉树的遍历

前面我们讲到，树其实是链表的升级，因此如果要考虑到对树的所有节点进行遍历，也就跟遍历链表是差不多的，但是与链表不同的是，树并不是线性的，如果要完整的遍历每一个节点，那么就需要设计一些特殊的遍历算法。

定义树节点：

因此我们根据对节点的访问顺序的不同，形成了以下几种算法：

层序遍历(广度优先):

前序遍历：

中序遍历：

后序遍历：

二叉树的数组表示

当树中节点数目较少时，我们也可以使用数组来实现树结构。

我们先来考虑一个完美二叉树，如果我们按照该完美二叉树的层序顺序映射到一个数组当中时，其各个节点在数组中的索引也就确定了，而且，我们也能够很容易得到索引为i的节点的子节点和父节点的索引：

左子节点索引

2i + 1

右子节点索引

2i + 2

父节点索引

(i−1)/2

如果我们考虑非完美二叉树，将其与之对应的完美二叉树对应，缺少节点的地方我们填入一个非法的值，来表示这里为空，我们就实现了利用数组实现二叉树。

二叉搜索树

二叉搜索树是在每个节点的值上具有一定特点的特殊二叉树，其满足的条件如下：

对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值；

任意节点的左右子树也满足条件1；

二叉搜索树的查找：

二叉搜索树的查找每次根据当前节点值与标准值的大小，排除掉一半的节点，是与二分查找算法的思想是一致的：

二叉查找树的插入：

向二叉查找树中插入元素，我们需要保证不能破坏二叉搜索树成立的条件，因此首先需要根据值的大小进行插入位置的查找，最后找到满足条件的叶子节点作为其父节点，再根据父节点的值决定将其放到左子节点还是右子节点；除此之外，还需要保证不能存在重复的节点。

二叉查找树的删除:

二叉查找树的删除操作与插入相似，同样需要保证不能破坏二叉查找树成立的条件。不过因为可能是删除非叶子节点，因此删除算法又较为复杂，我们分三种情况进行讨论：

如果被删除的度为0，即叶子结点，则可以直接删除；

如果被删除的度为1，则可以直接用其子节点代替该节点；

如果被删除的度为2，则：

利用左子树的最大节点来代替该节点；
利用右子树的最小节点来代替该节点；

对于第三种情况，我们假设使用左子树的最大节点来代替被删除节点：

在最后，我们需要注意的是，如果二叉树不是平衡的，那么在频繁的插入和删除之后，很可能就退化成了链表，这将极大地影响到后续操作的效率。

因此，我们便引入了AVL树的概念。

AVL树

AVL树，是一种平衡的二叉搜索树，所谓平衡，就是一棵树中所有节点的左右子树的高度之差不超过1。这里的高度，指的是当前节点到在当前分支上最远叶子节点所经过的边的个数，因此，叶子节点的高度为0，空节点的高度为-1。

如果一个二叉搜索树能够始终保持这种平衡的性质，那么它就很难退化到链表，导致各种操作的效率降低。

为了实现的方便我们需要定义一个平衡因子（balance factor），即左子树的高度减去右子树的高度。

AVL树的旋转调整：

在对AVL树进行插入或者删除操作的时候，为了保证其平衡的性质，而且要不改变中序遍历的节点顺序，就需要一定的结构调整算法，我们称之为旋转。

如果出现了失衡节点，即平衡因子的绝对值＞1的节点，我们需要对其进行调整。

旋转，就是对失衡节点进行调整，使其重新恢复平衡。

插入节点：

AVL树的插入操作的基本原理是与二叉搜索树非常不同的，其本质原因是因为其平衡性，在每插入一个节点之后，我们都需要向上回溯，自底向上检查每个节点是否失衡，并对其进行调整，因此我们必须使用递归：

删除节点也是一样：

堆

堆，是一种满足特定条件的完全二叉树，我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为堆底，其需要满足的特殊条件如下：

小顶堆：任何节点的值都不大于其子节点的值；

大顶堆：任何节点的值都不小于其子节点的值；

堆这个概念我可以说是第一次接触，虽然数据结构课上学过。如果一个堆是小顶的，那么其根节点一定小于其两个子节点，根节点的两个子树的根节点也一定小于其两个子节点，但是这两个根节点的大小却没有关系。如果要向其中插入元素，则只能顺序插入最底层。在插入之后，可能会破坏堆成立的条件，那么就要递归向上检查，若不满足条件则进行调整，直到满足条件为止。

堆的物理结构:

在二叉树那一节，我们提到了完全二叉树是最适合用数组表示的，因此我们可以使用数组来存储一个堆。

入堆：

出堆:

堆的建立

理论上来讲，我们可以通过不断地执行入堆操作，来实现将一个列表转化为一个堆的目的，入堆的操作的复杂度为log级，因此建堆的时间复杂度为: O(nlogn) 不过我们也可以利用一条性质，将建堆的操作的时间复杂度缩短到O(n)级别，性质如下：叶子结点的个数远远多于非叶子结点的个数。

图

图(graph)是一种不规则的非线性数据结构，由顶点(vertex)和边(edge)组成。图是由链表进化而来的一种高级且复杂的数据结构，相比于体现线性关系的链表以及分治关系的树，图体现的是一种自由度更高、更复杂的网络关系。

图的分类

根据图的一些边或者点上的特点，我们可以对图进行分类。

边是否需要考虑方向：有向图和无向图；

是否需要考虑边权重：无权图和有权图；

图的存储结构

邻接矩阵：

增删改查效率高，因为是数组，可以通过索引实现直接存储；
矩阵的空间利用率低，因为是一个完整的矩阵，可能会存储大量不存在的边；

邻接表：

节省空间，因为只需要存储存在的边；
时间效率不如邻接矩阵，因为使用的结构式链表，所以需要逐个遍历进行查找，可以将链表使用哈希表或AVL树来代替，提高效率；

图的遍历算法

广度优先遍历

顾名思义，该算法每次都需要遍历所有当前能够遍历到的所有的节点，即广，直至所有节点都被遍历到。该算法往往会使用到队列这种数据结构，因为我们需要利用已经访问到的节点继续进行下一层的访问，因此我们需要将被访问的节点暂时存储以下，直到当前层次的所有节点都被访问到后才开始进行。

深度优先搜索

顾名思义，该算法每次都会任意选择一个能够访问到的节点，立马向下层访问，直到某一步，无可访问，则返回上一步，寻找新的访问点，直到所有节点都被访问到为止。与“广”相对，该算法体现的是一个“深”字，即尽可能的深入，如果不能继续深入了我就换条路径继续深入，正因为这种特点，我们往往借用栈这种数据结构来进行实现，当然了，为了实现的简单性，我们也可以采用递归的思想。

基本算法

搜索

搜索的本质，就是从一个数据结构当中检索出满足特定条件的一个或一组元素，这里的数据结构可以是数组、链表、树、图等。

常见的搜索算法一般有两种：

遍历整个容器，搜索目标元素；

在容器中元素有序排列的情况下，使用二分算法，大大提高搜索效率；

二分查找

二分查找具有如下特点：

二分查找相比于线性遍历在时间上具有很大优势；

二分查找无需消耗额外空间，而哈希查找则需要额外的空间用于存储记录；

二分查找只适用于容器中元素有序的情况下进行；

二分查找需要随机访问元素，因此一般只适用于数组结构；

当数据量较小时，其效率可能不如线性查找；

二分算法的本质其实就是通过维护左右两个指针，使其分别向大于等于目标元素和小于等于目标元素的位置靠近，因此如果不存在target元素的化，left最终会指向首个大于target的元素，right会指向首个小于target的元素。

哈希查找

哈希查找就是通过建立一个哈希表，避免了频繁重复查找元素带来的时间上的冗余。

排序

为什么要对数据进行排序？因为有序的数据便于进行高效地查找、分析和处理。

评价排序算法的五大维度：

运行效率（时间）；

就地性（空间）；

稳定性：在完成排序后，相等元素在数组中的相对位置是否会发生改变；

自适应性：自适应排序的时间复杂度会收到输入数据的影响，即最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相等；

排序算法是否是基于比较的：基于比较的排序依赖比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，其理论最优时间复杂度为O(nlogn)。而非比较排序不使用比较运算符，时间复杂度可达O(n)，但其通用性较差。

选择排序

找到数组中最小的元素，并把它与第一个元素交换，并重复做此行为，最终得到一个升序的序列。

选择排序是不稳定的。

冒泡排序

冒泡排序是稳定的。

插入排序

插入排序是稳定的。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 O(n^2)，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。

选择排序在任何情况下的时间复杂度都为O(n^2)。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。

选择排序不稳定，无法应用于多级排序。

快速排序

快速排序的基本思想是：从当前数组中任选一个值来作为一个基准值，通过不断地比较与交换来使得基准值的左边是小于基准值的数，基准值的右边是大于基准值的数。

为了实现的方便性，我们往往会选择数组最左侧的元素作为基准值base，然后维护两个指针i和j，使其分别从数组的两边开始，i负责寻找第一个小于base的数，j负责寻找第一个大于base的数，然后将两者交换，这就将小于base和大于base的数放到了两边；要注意，每次交换完成后，i和j指向的地方一定是已经完成处理的区域，因此如果i和j相交，那么一定是已经完成了整个数组的处理，此时将base与i值进行交换，我们就完成了左边 < base < 右边的排序。注意，如果遇到与base相等的值，则不需要处理。

快速排序使用了分治的思想策略。

时间复杂度为O(nlogn)、是一种自适应排序，如果每轮划分都将整个数组划分为0和n-1两个子数组，那么时间复杂度将会达到O(n^2)。

由于需要递归，因此空间复杂度为O(n)；

原地排序，为借助辅助数组；

非稳定排序；

快速排序在效率方面是有一定优势的，尽管快速排序的平均时间复杂度与“归并”和“堆”相同：

出现最差情况的概率很小；

缓存利用更高效；

复杂度的常数系数小；

基准值选取优化：

为了避免时间效率恶化的情况，我们要对基准值的选取进行一定的优化：我们采取的策略是，从最左边、最中间和最后边各取一个数，得到它们三个的中值，并将这个中值交换到最左侧，继续进行算法。

归并排序

归并排序采用的策略也是分治，首先通过将整个数组一分为二，将两个数组各自排序之后，在利用合并算法将两个子数组进行合并，就得到了整个数组的排序结果。当然了，对数组的划分也是递归地进行的，通过不断地划分，最后会得到只包含一个元素的子数组，此时停止划分，开始合并。

算法特点如下：

时间复杂度为O(nlogn)，是一个非自适应排序，非常稳定；

空间复杂度为O(n)，非原地排序；

是一个稳定排序；

除此之外，归并排序非常适合链表的排序。

堆排序

时间复杂度为O(nlogn)，是一个非自适应排序；

空间复杂度为O(1)，是一个原地排序；

是一个非稳定排序；

桶排序

前几种算法都是所谓的“基于比较的排序算法”，即都是通过比较元素间的大小来实现排序，从理论上来说，此类排序算法的时间复杂度无法超越O(nlogn)。

桶排序是分支策略的一个典型应用，通过设置一些桶，将数据尽量平均费配到各个桶中，分别对各个桶进行排序，最后将每个桶进行合并，这个过程有点像搭积木，先搭身子和头，再将两者对接起来。

排序特点：

时间复杂度可以达到O(n+k)，即如果元素平均分配在k个桶中，每个桶的元素为n/k个，如果排序单个桶的时间复杂度为O(n/k logn/k)如果k比较大，则趋向于O(n)。合并需要话费O(n+k)的时间。

是一个自适应排序，如果所有的元素都分配到同一个桶中，则复杂度发生退化。

空间复杂度为O(n+k)，是一个非原地排序；

桶排序是否稳定取决于排序桶内元素的算法是否稳定，因为相等的元素一定会分配到同一个桶内；

我们可以注意到，桶排序的效率往往取决于桶的设置是否合理，元素的分配是否平均：

可以先将元素大致划分到3个桶中，再对元素过多的桶在进行划分，直到所有的桶中元素的数量相近位置；

当然了，我们也可以利用元素大小的统计信息来大致划分数据。

计数排序

计数排序是桶排序的一个特例。

计数排序首先需要找出所有整数中的最大值max，再声明一个max+1大小的计数数组counter，以每个num为key，num出现的次数为value存储进counter数组中，然后计算counter数组的前缀和数组，因为每个前缀和 - 1表示这个值在排序后的数组中最后出现的索引，随后遍历整个nums数组，根据每个num找出对应的前缀和，放到排序后数组中的对应位置，并将该前缀和-1，最后得到结果。

算法特点：

时间复杂度为O(n+m)，如果n>>m，时间复杂度趋于O(n)；

空间复杂度为O(n + m)，是一个非原地排序；

是一个稳定排序，不过需要保证最后对nums数组的遍历必须是逆序的；

局限性如下：

由于牵扯到索引，所以只适用于非负整数；

计数排序适用于数据量大但是数据范围小的情况；

基数排序

基数排序是对每个元素逐位进行排序，最后得到排序结果，每次排序其实都是一个计数排序。

时间复杂度为O(nk)，k为最大位数，如果k过大，效率则迅速降低；

空间复杂度为O(n+d)，是一个非原地排序；

是一个稳定排序，因为计数排序稳定；

分治算法

所谓分治，就是将一个大的问题，独立的分为多个较小的问题，独立地解决所有的小问题之后，再将所有的小问题进行合并，得到大问题的解。

分治算法之所以比普通算法更高效的原因，就在于其不断地减小数据量，并最后利用一个并不复杂的算法进行合并，而这往往比直接对整个数组进行排序高效的多。

从另一方面来讲，分治将一个大问题分解为多个小问题进行解决的方式，一般通过程序的递归结构来实现。

构建树问题

在讲义中所提及的构建树问题是：给出一个树的先序遍历和中序遍历，构建出完整的二叉树。

要想判断这个问题是否可以利用分治的思想解决，必须判断其是否具备分治的条件：

问题是否是可分解的？构造一颗完整的二叉树，我们可以将其分解为识别出根节点、构造左子树、构造右子树三个小问题；

小问题是否可以独立解决？显然是可以的；

小问题的解是否可以合并为大问题的解？显然也是可以的。

因此我们只要对当前的树完成以上三个小问题，再递归下去，就能得到一颗完整的二叉树。

如果我们知道了一棵树的先序遍历序列和中序遍历序列（树无重复值），我们的构造逻辑如下：

先序遍历序列的第一个节点一定是根节点；

根据根节点的值，找到根节点在中序遍历中的位置；

先序遍历序列的结构：[根节点|左子树节点|右子树节点]；

中序遍历序列的结构：[左子树节点|根节点|右子树节点]；

存在这样一条逻辑：知道了根节点的值，就可以将中序序列的结构划分出来，进而根据中序序列的划分结构，就可以根据左右子树的数量将先序序列划分出来。

回溯算法

之所以称为回溯算法，是因为该算法在搜索空间时采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他的可能。

剪枝

所谓“剪枝”，顾名思义，就是剪去不必要的枝条，在回溯算法中是只通过特殊条件的设定来避免不必要或不满足要求的解。

总体来讲，回溯算法就是包括三个部分：剪枝、尝试和回退。在回溯算法的进行过程中，其实存在一个解的当前状态state，而且我们还有若干个选择，在执行某个选择前，我们首先需要判断该选择是否满足要求，也就是剪枝，如果是，那么则执行此选择，进行尝试，改变解的状态，随后问题的解进入了一个新的状态，因此我们需要对新的状态进行尝试，如果对当前的选择的尝试完成了，我们就需要进行下一个选择的尝试，因此首先需要回退状态，使得解的状态退回到尝试前。

全排列问题

全排列问题其实就是一个多次选择的问题，一个元素个数为n的集合的全排列，就是进行n次随机选择的所有可能的情况，这个问题需要考虑如下逻辑问题：

问题的状态就是已经选择了的前部分序列；

问题的选择就是未被选出的元素；

尝试就是从剩余元素中选出一个元素，产生新状态；

当尝试之后，回退状态；

这里的问题的状态其实包括两个部分，一个是已经确定的序列，另一个是selected数组，selected[i]用于记录第i个元素是否被选出来了，防止多次重复选取相同的元素。

子集和问题

子集和问题中有多种剪枝：

由于对数组的遍历是顺序的，因此会产生形如[4,5]和[5,4]的重复结果。因为我们使用的是深度优先遍历的思想，所以对索引靠前的元素会优先进行遍历，例如：对于[1,4,2,3,5]数组，第一轮的选取一定是[1,…]，包括[1,…,3,…]、[1,…,4,…]等，而后面出现的[4,…,1,…]、[3,…,1,…]就会出现重复。为了避免这种情况，对索引靠后的元素进行搜索时，就无需对此元素之前的元素进行搜索了。（也就是保证了结果的索引是非递减的）

考虑到集合中存在重复元素的情况，我们只需要在每次选择时，避开已经尝试过的元素即可，可以用一个哈希表来实现；

对于尝试之后元素和大于target的选择，直接跳过；

动态规划

讲义中举出的例子是上楼梯问题，这个问题当然可以用回溯算法解决，即将当前决策序列作为解状态state，将能够选择的阶数作为choices，然后不断地进行尝试、回退，最终得出问题的解，其时间复杂度是指数阶的。

当然，我们也可以利用递推的方式：total[i] = total[i - 1] + total[i - 2]，即到达i阶层的方案总数等于到达i - 1阶层的方案总数加上到达i - 2阶层的方案总数。不过其时间复杂度依旧是指数阶的，与回溯算法一样。不过仔细分析这种算法的特点，发现total[i-1]递推得到total[i - 2] + total[i - 3]，这里的i - 2就与源表达式中的i-2重复了，导致同样的东西算了两次，因此我们就引入了记忆化搜索：当算出到达i层的方案总数算出来后，保存到mem[i]中，使得下一次计算i层方案总数时，直接从mem[i]中取出，这样算法的时间复杂度就被优化到了O(n)级别，非常高效。

显然，记忆化搜索是一种自顶向下的算法，与之相反，动态规划则是一种自底向上的算法，只要知道了最小问题的解，也就是迭代的初始状态，就可以通过状态转移方程，迭代得到最终问题的解。

动态规划的基本特性

最优子结构：原问题的最优解是从子问题的最优解构建得来的；

无后效性：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关；

这里可能需要着重注意一下无后效性，如果问题描述中存在较多的约束，使得状态的未来发展不仅只与当前的状态有关，例如可能和上一个状态有关，那么我们可能就要扩展问题的状态，使得dp升维，用于记录更多不同情况下的问题的解。

贪心算法

所谓贪心算法，顾名思义，就是非常的贪心，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。

其与动态规划算法的区别在于：

动态规划会根据之前的所有的决策来考虑当前决策，并使用过去子问题的解来构建当前子问题；

贪心算法则不会考虑之前的决策，而只是不断地贪心地进行选择，不断缩小问题范围，以期获得问题的解。

一般情况下，贪心算法的适用情况分以下两种。

可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。

可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的。

相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质。

贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。

最优子结构：原问题的最优解包含子问题的最优解。

贪心问题的解决流程大体可分为以下三步。

问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及。

确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。

正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。

算法杂项

快速幂算法

拓展：矩阵的快速幂算法

数论初步

最大公约数——欧几里得辗转相除法

gcd(a, b) = gcd(b, a % b)

最小公倍数

a * b = gcd(a, b) * lcm(a, b)

素数的判定

素数的定义如下：

素数是一个正整数；

素数除了1和它本身，没有其他因子；

1不是素数

一个关于合数的定理：

如果一个数是合数，那么一定有两个数p1 ≤ sqrt(n)，p2 ≥ sqrt(n)，使得p1 * p2 = n，其中p1和p2是n的因子。

因此如果要判断一个数为素数，只需要判断2 ~ sqrt(n)中是否有其因子即可。