问题求解的关键
问题建模
对输入参数和解给出形式化或半形式化的描述
设计算法
选择什么算法？如何描述这个方法？
这个方法是否对所有实例都得到正确的解？如何证明？
如果不是，能否找到反例？
分析算法
分析算法的效率
NP难问题
- NP-hard问题有数千个，大量存在于各个应用领域。NP-hard问题举例：TSP问题、0-1背包、双机调度
- 目前还没有找到有效算法，有效算法指的是运行时间是输入规模$n$的指数或更高阶函数，即输入规模$n$的多项式时间。
- 至今没有人能证明这类问题不存在多项式时间的算法。
- 从是否存在多项式时间算法的角度来看，这些问题是彼此等价的（如果其中一个问题存在多项式时间的算法，则其它问题也都存在；如果其中一个不存在，则其它问题也不存在多项式时间算法）。这些问题的难度处于可有效计算的边界。
问题
定义
需要回答的一般性提问，通常含若干参数
问题描述
- 定义问题参数（可以是集合、变量、函数、序列等等）
- 说明每个参数的取值范围和参数间的关系
- 定义问题的解
- 说明解满足的条件（优化目标或约束条件）
问题实例
参数的一组赋值可得到问题的一个实例
算法
定义
有限条指令的序列，这个指令序列确定了解决某个问题的一系列运算或操作。
要求
若算法A解问题P，则应满足：
- 把问题P的任何实例作为算法A的输入，都可输出该实例的正确解
- 每步计算是确定性的
- A能够在有限步停机
基本运算
可以是比较、加法、乘法、置指针、交换等等操作。
基本运算的确定往往和输入规模相关，算法基本运算的次数可表示为输入规模的函数。
排序
元素之间的比较
检索
被检索元素$x$与数组元素的比较
整数乘法
每位数字相乘（位乘）1次，$m$位和$n$位整数相乘要做$mn$次位乘
矩阵相乘
每对元素乘1次
$i\times j$矩阵与$j\times k$矩阵相乘要做$ijk$次乘法
图的遍历
置指针
时间复杂度
针对指定的基本运算，算法所做基本运算的次数。
对于相同输入规模的不同实例，算法的基本运算次数也不一样，我们可定义以下两种时间复杂度。
最坏情况下的时间复杂度$W(n)$
算法求解输入规模为$n$的实例所需要的最长时间
平均情况下的时间复杂度$A(n)$
在给定同样规模为$n$的输入实例的概率分布下，算法求解这些实例所需要的平均时间
设$S$是规模为$n$的实例集，实例$I\in S$的概率是$P_I$，算法对实例$I$执行的基本运算次数是$t_I$，则$A(n)=\sum_{I\in S}P_It_I$
输入规模
通常用数组元素多少、调度问题的任务个数、图的顶点数和边数等表示
排序
数组中元素个数$n$
检索
被检索数组的元素个数$n$
整数乘法
两个整数的位数$m$和$n$
矩阵相乘
矩阵的行列数$i,j,k$
图的遍历
图的顶点数$n$，边数$m$
给定问题和基本运算就决定了一个算法类
比如排序问题，以元素间的比较为基本运算，就确定了一个算法类。
伪码描述
赋值语句
$\leftarrow$
分支语句
if…then..…[else..…]
循环语句
while，for，repeat，until
转向语句
goto
输出语句
return
调用
直接写过程的名字
注释
//..…
作者：@臭咸鱼
转载请注明出处：https://chouxianyu.github.io
欢迎讨论和交流!