计算理论计算复杂性2016ppt课件.pptx

《计算理论计算复杂性2016ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教材:[1][王]王晓东,计算机算法设计与分析(第4版),电子工业.[2][S]唐常杰等译,Sipser著,计算理论导引,机械工业.参考资料:[3][C]潘金贵等译,Cormen等著,算法导论,机械工业.[4][M]黄林鹏等译,Manber著,算法引论-一种创造性方法,电子.[5][刘]刘汝佳等,算法艺术与信息学竞赛,清华大学.[6][L]Lewis等著,计算理论基础,清华大学.计算理论与算法分析设计刘庆晖计算理论第三部分计算复杂性第7章时间复杂性1.时间复杂性{0k1k

2、k0}的时间复杂性分析2.不同模型的运行时间比较单带与多

3、带确定与非确定3.P类与NP类4.NP完全性及NP完全问题一.时间复杂度时间复杂度定义{0k1k

4、k0}的时间复杂度分析时间复杂性判定器M的运行时间或时间复杂度是f:NN,f(n)是M在所有长为n的输入上运行的最大步数.若f(n)是M的运行时间,则称M在时间f(n)内运行或M是f(n)时间图灵机举例:大O与小o记法对于函数f,g:NR+,记f(n)=O(g(n),若存在c>0使得记f(n)=o(g(n)),若分析算法讨论语言A={0k1k

5、k0}的复杂性:M1=“对输入串w:1)扫描带,如果在1的右边发现0,则拒绝.2)如果0

6、和1都在带上,就重复下一步.3)扫描带,删除一个0和一个1.4)如果带上同时没有0和1,就接受.”时间分析:(1)2n=O(n),4)n=O(n),{(2)2n=O(n)+(3)2n=O(n)}(n/2)=O(n2)所以M1的运行时间是O(n2).时间复杂性类定义:对于函数t:NN,时间复杂性类TIME(t(n))定义为:TIME(t(n))={L

7、存在O(t(n))时间TM判定L}因为M1是时间O(n2)图灵机,所以A={0k1k:k0}TIME(n2).是否存在更快的TM判定A呢?图灵机M2M2=“对输入串w:1)扫描带,

8、若1的右边有0,则拒绝.2)若0,1都在带上,重复以下步骤.3)检查带上0,1总数的奇偶性,若是奇数,就拒绝.4)再次扫描带,第1个0开始,隔1个0删除1个0;第1个1开始,隔1个1删除1个1.5)若带上同时没有0和1,则接受.否则拒绝.”O(n)O(n)O(n)O(n)O(n)logn总时间:O(nlogn){0k1k

9、k0}TIME(nlogn)由图灵机M2知道ATIME(nlogn)有没有更快的图灵机识别A?对于单带确定图灵机,由定理:时间o(nlogn)的单带图灵机判定的语言是正则语言.TIME(o(nlogn))

10、正则语言类TIME(n)正则语言类=TIME(n)=TIME(o(nlogn))非正则语言{0k1k

11、k0}TIME(o(nlogn))二.不同模型的时间复杂度比较单带与多带确定与非确定单带与多带运行时间比较{0k1k

12、k0}有O(n)时间双带图灵机M3=“对输入串w:1)扫描1带,如果在1的右边发现0,则拒绝.2)将1带的1复制到2带上.3)每删除一个1带的0就删除一个2带的1.4)如果两带上同时没有0和1,就接受.”定理:设函数t(n)n,则每个t(n)时间多带TM和某个O(t2(n))时间单带TM等价.{0k1k

13、k

14、0}的O(n)时间双带图灵机q0q1└┘qaq2└┘└┘└┘└┘NTM的运行时间定义:对非确定型判定器N,其运行时间f(n)是在所有长为n的输入上,所有分支的最大步数....f(n)接受/拒绝...f(n).........TMNTM定理:设t(n)n,则每个时间t(n)NTM都有一等价的时间2O(t(n))TM.NTIME(t(n))TIME(2O(t(n)))三.P与NP多项式时间运行时间相差多项式可以认为是小的相差指数可以认为是大的.例如:n3与2n,对于n=1000.有关素性测试:Prime={p

15、p是素数}如何编码?一进

16、制,二进制,十进制?典型的指数时间算法来源于蛮力搜索.有时通过深入理解问题可以避免蛮搜.2001年Prime被证明存在多项式时间算法.P类定义:P是单带确定TM在多项式时间内可判定的问题,即P=kTIME(nk)P类的重要性在于:对于所有与单带确定TM等价的模型,P不变.P大致对应于在计算机上实际可解的问题.研究的核心是一个问题是否属于P类.NP类NTIME(t(n))={L

17、L可被O(t(n))时间NTM判定.}定义:NP是单带非确定TM在多项式时间内可判定的问题,即NP=kNTIME(nk)EXP=∪kTIME(2^(nk

18、))PNPEXPPEXP一些P问题有些问题初看起来不属于P求最大公因子:欧几里德算法,辗转相除法模p指数运算abmodp素性测试等等以增加空间复杂性来减小时间复杂性上下文无关语言有O(n3)判定器快速验证HP={<