# 算法
# 算法
离散数学中有多种一般性问题。例如，已知一串整数，求最大的一个；已知一个集合，列出其所有子集；给定一个整数集合，把这些整数从小到大排序；已知一个网络，找出两个顶点之间的最短路径等。遇到这样的问题时，首先要做的就是构造一个模型把问题转换为数学问题。
建立合适的数学模型只是解题的第一步。完整的解题还需要利用这一模型解决一般性问题的方法。理想的情况是需要一个过程，它能够遵循一系列步骤导致找到所求的答案。这一系列步骤就称为一个算法（algorithm）
定义：
『 算法 』是进行一项计算或解决一个问题的准确指令的有限序列。
例子：
例子：
# 搜索算法
在有序表中定位一个元素的问题经常会出现在各种应用场景。例如检查单词拼写的程序要在字典中搜索，而字典其实就是单词的有序表。这一类问题称为搜索问题。
# 线性搜索
# 二分搜索算法
当表中的各项是顺序排列的 ，可以使用二分搜索算法。它是通过比较要搜索的元素与表的中间项进行的。然后此表就分成两个较小的长度相等的子表，或其中较短的列表比另一个少一项。根据与中间项的比较结果，可以将搜索局限于一个合适的子表继续进行。
# 排序
# 冒泡排序
# 插入排序
# 贪婪算法
最优化问题（optimization problem）这种问题的目标是寻找给定问题满足某个参数值最小化或最大化的解。
🌰 例如，寻找两个城市之间总里程最短的路线；确定一种用尽可能少的位数进行消息编码的方式；以及寻找一组在网络节点之间使用最少量光纤的光纤连接。
例子：
贪婪算法根据某一条件在每一步都做出最佳选择。下面的例子表明在多个条件中选择哪一个也可能是难以确定的。
例子：
# 停机问题
现在我们来描述计算机科学中非常有名的一个定理的证明。我们将要证明存在这样一个问题，它不能用任何过程求解。即我们要证明存在不可解问题。
我们要研究的问题是停机问题（halting problem）它询问是否存在一个过程（procedure）能做这件事: 该过程以一个计算机程序以及该程序的一个输入作为输入，并判断该程序在给定输入运行时是否最终能停止。
显然，如果真的存在，有这样一个过程是非常方便的。在编写或者调试程序的时候，能够判断一个程序是否进入无限循环是非常有帮助的。然而，1936 年图灵证明这样的过程是不存在的
# 函数的增长
解决一个问题所需的时间不仅仅取决于所用的操作步数。这个时间还取决于用于运行实现一个算法的程序的硬件和软件。但是，当我们更改用于实现算法的硬件和软件时，可以通过给先前估计所需时间乘以一个常数来精确地估算求解规模为 n 的问题所需的时间。例如，在一台超级计算机上求解规模为 n 的问题可能比在一台个人计算机上快 100 万倍。而这 100 万的因子并不取决于 n。
使用 大 O 记号（big O natation）有一个好处，就是可以估计一个函数的增长而不用担心常数因子或低阶项。这意味着使用大 O 记号不用担心实现算法所用的硬件和软件。另外，使用大 O 记号时我们可以假设算法中使用的不同操作都花费相等的时间，这大大简化了分析。
大 O 记号广泛用于估计当输入增长时一个算法所用的操作的数量。借助于这个记号，就能够判定当输入规模增大时用一个特定算法来求解该问题是否实际可行。另外，使用大 O 记号，可以比较两个算法以判断当输入规模增大时哪个算法更有效。
# 大 O 记号
定义：
例子：
例子：
# 一些重要函数的大 O 估算
定义：
现在举几个与定义域为正整数集的函数有关的例子：
例子：
# 函数组合的增长
定义：
例子：
# 大 Ω 记号 & 大 Θ 记号
定义：
例子：
定义：
例子：
# 算法的复杂度
# 时间复杂度
例子：
# 最坏情形复杂度
例子：
# 平均情形复杂度
例子：
# 矩阵乘法的复杂度
例子：
例子：
# 算法范型
所谓算法范型就是基于一种特定概念的通用方法，可以用来构造求解一类广泛问题的算法。
本节我们就介绍一个被称为 “蛮力” 的算法范型。
在蛮力算法（brute-force algorithm）中，问题是通过基于对问题的描述和术语的定义以最直接的方式解决的。设计蛮力算法来解决那些不太在意所需计算资源的问题。例如在某些蛮力算法中，一个问题的求解是通过检查每一种可能的解，然后找出最可能的解。一般情况下，蛮力算法是朴素的问题求解方法，而不需要利用问题的任何特殊结构或聪明的点子。
之前讲过的线性查找，冒泡 排序，插入排序都属于蛮力算法。
虽然蛮力算法通常比较低效，但通常却非常有用。蛮力算法是能够解决实际问题的，特别是当输入规模不是很大时，即使对于大规模的输人会变得不切实际。再者，当设计新算法来解决一个问题时，目标通常是寻找一个比蛮力算法更有效的算法。
例子：
# 理解算法的复杂度
例子：
# 易解性
# P 与 NP
# 实际的考虑
