第一章：算法的概念
本章学习目标如下：
1.什么是算法？
2.算法在最好情况、最差情况还有平均情况下的计算复杂度。
3.掌握算法复杂性渐近态的数学表达式。
4.了解NP问题的基本概念。
一．法概述——什么是算法
1.算法的定义：是一系列解决问题的明确指令，即对符合一定的规范的输入，能够在有限的时间内获得输出。
2.算法的特征：
输入：有零个输入或者多个输入。
输出：至少有一个输出。
确定性：组成算法的每条指令清晰明确、无歧义。
有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
3.程序是什么？程序跟算法有什么区别？
答：程序是算法用某种程序设计语言的具体实现；程序可以没有算法的有限性；算法与描述形式无关。
区别：①形式不同.算法是描述在一般使用的语言；程序.程序是用在形式化的计算机语言描述的。②性质不同.算法是解决问题的步骤；程序是代码的实现。③特点不同.算法需要程序来完成功能；程序需要算法作为灵魂。
二．算法概述——如何描述算法
伪代码、自然语言、程序语言还有流程图等。
例子：伪代码如下
伪代码是：介于计算机语言跟自然语言之间的文字跟符号来描述算法。
控制表达式如下：
If...them...[else...]
While...do...
Repeat...until...
For...do...
缩进代替花括号
表达式如下：
←表示赋值
=相等测试
函数描述：
算法名称 （参数【，参数...】）
输入...
输出...
函数调用：
算法名称 （参数【，参数...】）
返回值
Return 表达式
三．算法概述——如何评价 算法
1.正确性：一切合法的输入数据都能得出满足要求的结果。
2.可读性：算法易于人的理解。
3.健壮性：算法异常情况的处理。
4.高效率跟低存储量：执行算法的时间、占用内存的空间。
5.分析算法占用计算机占用计算机资源的情况，两个方面时间复杂的T(n)跟空间复杂的S（n）.
算法的分析如下(重中之中）：
算法的复杂度分为时间复杂度T（n）跟空间复杂度S（n）
T（n):O(1)称为常数级；
O(logn)称为对数级；
O（n)称为线性级；
O（nlogn)
O（n^c)称为多项式级；
O（c^n)称为指数级；
0（n!)称为阶乘级；
算法的复杂度有：最好情况、最差情况还有平均情况。
渐近分析有如下三种：
O:渐近上界
当N>=N0时，有f（N）<=Cg(N)记为f(N)=O(g(N))
Ω：渐近下界
当N>=N0时，有f（N）>=Cg(N)记为f(N)=Ω(g(N))
Θ：渐近紧确界
当且仅当f（N)=O(g(N))且f(N)=Ω(g(N)）记为f(N)=θ(g(N));
四．算法的概述——算法的分类
五．NP完全性理论
P类问题：所有可以在多项式时间内可以求解的判断性问题构成P类问题。
NP问题：所有非确定性多项式时间内可以求解的判断性问题构成NP问题。
NP难问题：需要超多多项式时间才能求解的问题。
NP包含P