一、算法分析引言

《一、算法分析引言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章预备知识1.1引言---理论上的可计算与现实上的可计算一、理论上的可计算――可计算性理论合理的计算模型：递归函数、Turing机、λ演算、Post系统等Church-Turing论题：直观上可计算的函数是递归函数。直观上可计算的函数是Turing机可计算的函数人们已经证明了所提出的各种合理的计算模型在可计算的能力方面都与Turing机等价。尽管人们还不能给出Church-Turing论题的形式证明，但是这些事实说明可计算性本身是不依赖于计算模型的客观性质。二、现实上的可计算――计算复杂性理论理论上可计算的函数不一定在现实上是可计算的，因为计算这些函数需要太多的

2、资源，即计算时间或存储空间。换句话说，求解这个问题的算法的时间或空间复杂性太高。需要在理论上分清那些函数是现实上可计算的。1．问题：需要回答的一般性提问，通常含有若干参数。问题描述所包含的内容：对问题参数的一般性描述，解满足的条件问题的实例：对问题的参数的一组赋值例1巡回售货员问题：有穷个城市的集合C={c1,c2,…,cm},正整数d(ci,cj)=d(cj,ci),1≤i,使得k1,k2,…,km是1,2…,m的置换且满足k1k2kmm−1min(∑d(cki,cki+1)+d(ckm,ck1))i=1实例：C={c1,c2,c3,

3、c4},d(c1,c2)=10,d(c1,c3)=5,d(c1,c4)=9,d(c2,c3)=6,d(c2,c4)=9,d(c3,c4)=32．算法非形式定义有限条指令的集合，这个指令集确定了解决某个问题的运算或操作的序列。满足以下条件：输入个数大于等于0;输出个数大于0;具有确定性,即每条指令无歧义，多次执行是可以重复的;指令有限条，即每条指令执行次数和执行时间有限.形式定义对所有的有效输入停机的Turing机.算法A解问题P：把问题P的任何实例作为算法A的输入，A能够在有限步停机，并输出该实例的正确的解。3．算法的时间复杂性最坏情况下的时间复杂性：算法求解输入规

4、模为n的实例所需要的最长时间W(n)平均情况下的时间复杂性：算法求解输入规模为n的实例所需要的平均时间A(n)复杂性表示：一般针对问题选择基本运算，将基本运算次数表示为输入规模的函数。例2搜索问题输入：非降顺序排列的数组L，元素个数为n，数x.输出：j.若x在L中，j是x首次出现的序标；否则j=0以算法对于输入规模为n的数组所做比较次数来度量时间复杂性。算法为顺序搜索，假设x在L中的概率为p，并且x在L中不同位置是等概分布的，则W(n)=nnpp(n+1)A(n)=∑i+(1−p)n=+(1−p)ni=1n24.函数的阶设f和g是定义域为自然数N上的函数。若存在正数

5、c和n0使得对一切n≥n0有0≤f(n)≤cg(n),记作f(n)=O(g(n)).若存在正数c和n0使得对一切n≥n0有0≤cg(n)≤f(n),记作f(n)=Ω(g(n)).若对所有正数c存在n0使得对一切n≥n0有0≤f(n)

6、cn≤n—3n≤dn21311那么c≤—≤d,则d≥,n≥1;c≤,n≥7.2n21411取c=,d=,n0=7即可。1425.多项式时间的算法与指数时间的算法多项式时间的算法：时间复杂性为O(p(n))的算法，其中p(n)是n的多项式。指数时间的算法：不存在多项式p(n)使得该算法的时间复杂性为O(p(n))下表反映了多项式时间的算法与指数时间算法的区别表1时间复杂问题规模性函数102030405060－5－5-5-5-5-5N102*103*104*105*106*102-4-4-4-4-4-4n104*109*1016*1025*1036*103-3-3-3-

7、3-3-3n108*1027*1064*10125*10216*105-1n103.224.31.7分5.2分13.0分n2.001秒1.0秒17.9分12.7天35.7年366世纪n8133.059秒58分6.5年3855世纪2*10世纪1.3*10世纪表2时间复杂1小时可解的问题实例的最大规模性函数计算机快100倍的计算机快1000倍的计算机NN1100N11000N12NN210N231.6N23NN34.64N310N35NN42.5N43.98N4n2N5N5+6.64N5+9.97n3N6N6+4.19N6+6.296.问题的复杂性分析――多项式时间