文档介绍：算法和算法复杂性
第1页，本讲稿共32页
图灵机中无限长的带被分成一个个小空格，每格容纳一个符号，对每一部图灵机而言，带上允许使用的符号是有限的；
图灵机的输入是由符号组成的有限序列，称之为符号行，输入符号行不能果存在一个常数c>0,使得当n足够大时有f(n)≥cg(n),则记f(n)=Ω(g(n))；
第12页，本讲稿共32页
求出一个算法所需时间比较好上界
的过程称为算法分析。
算法分析中常常使用初等运算——算术运算、比较、转移指令等的步数表示一个算法在假设的计算机上执行时所需的时间，即每做一次初等运算，需要一个单位时间。而用算法的输入规模的函数度量该算法的复杂性。
第13页，本讲稿共32页
为了把输入提供给计算机求解，必须用固定字母表（0，1，或打字机上的符号，或ASCII字母）上的符号串来表示它们，这就是所谓的编码。当把算法的输入表示为符号串时，那麽输入规模就定义为该符号串的长度（符号串中符号的数目），称为输入长度。
第14页，本讲稿共32页
例1．以某一个固定数为基底的运算系统（如十进制或二进制）中，表示一个整数n的输入规模：，因为logBn=logn/logB, B固定后logB是一个常数。
.
设A、b、c中的元素均为整数，则LP的规模就是表示A、b、c所需符号的数目。因为可以把二进制（十进制）表示的矩阵中元素排成一行，用符号线适当地隔开以表示矩阵的行或列，从而矩阵也可以表示为符号串。所以，m×n的LP问题规模为Θ(mn+ ）其中p是所有非零参数的乘积。
第15页，本讲稿共32页
（3）多项式时间算法
①决定一个算法的实际效用，要看其已知的最好时间上界之增长速度。目前计算机科学家们有一个公认的看法：解一个计算问题的算法，当其复杂性随输入规模的增加而呈多项式地增长时，这个算法才是实际有效的。
第16页，本讲稿共32页
②定义（多项式算法）设有解某种问题的一个算法，对于输入长度为L的具体问题，其计算步骤有一个上界P（L），若P（y）是y的多项式，则称此算法是一个多项式时间算法（Polynomial-Time Algorithm for Linear Programming），简称多项式算法。
第17页，本讲稿共32页
函数
近似值
N
Nlogn
n3
106n8
10
33
1000
1014
100
664
1000，000
1022
1000
9966
109
1030
2n
nlogn
n！
1024
2099
3，628，800
1．27×1030
1．93×1013
10158
×10301
×1029
4×102567
③特点:
表1 多项式和指数函数增长情况表
当输入规模增大时，任意一个多项式算法终将变得比指数算法更有效，见表1。
第18页，本讲稿共32页
在某种意义上，它很好地利用了技术发展的优点。
每次技术突破，计算机速度提高10倍，则多项式算法原来1小时内所能解算例子的最大规模可增加C倍，其中0<C<10,而指数算法所能解算的例子规模只能增加一个常数.
表2显示了多项式算法利用技术发展的优点情况.
第19页，本讲稿共32页
表2 多项式算法利用技术发展的优点情况表
函数
一天内能解例子的规模
计算机速度提高10倍后所能解例子的规模
n
nlogn
n2
n3
108n4
1012
×1011
106
104
10
1013
×1012
×106
×104
18
2n
10n
nlogn
n!
40
12
79
14
43
13
95
15
第20页，本讲稿共32页
多项式算法有较好的封闭性——
n个多项式算法可以结合起来解同一问题的某些