0%

第一章概述

算法复杂性分析

算法渐近复杂性

渐近(不严格小/大)
渐近上界\(O\)

渐进下界\(\Omega\)

非紧(严格小/大)
非紧上界\(\omicron\)

非紧下界\(\omega\)

紧渐近界\(\Theta\)

注:上面符号与其说表示的是一个函数,不如说表示的是一个函数簇

总结

渐近的性质

传递性

反身性

互对称性:一个是另一个的上界,另一个就是一个的下界

对称性

算术运算

NP理论

基本定义

  • P:可以在多项式时间解决的问题

  • NP:目前没有多项式时间解决的算法,但是如果给出一个候选答案,可以在多项式时间里验证这个答案是不是正确的。

  • NPC:满足两个性质:

  1. 可在多项式时间验证候选答案(是NP问题);

  2. 任何一个NP问题可在多项式时间内规约到该问题。

  3. 重要性质:如果一个NP完全问题能在多项式时间内得到解决,那么NP中的每一个问题都可以在多项式时间内求解,即P=NP。

  • NP-Hard:任何一个NP问题可在多项式时间内规约到该问题,但无法证明问题本身是NP问题。NP-Hard至少和NP问题一样难。

典型NPC问题