第一講：計算復雜性理論

(ComplexityTheory)

計算量的概念計算量的表示算法與計算量計算復雜性影響計算復雜性的因素

優化問題及其計算的復雜性

例：組合優化問題：組合數雖然有限，但因其數量太多，尋找最優解很難。背包問題（knapsackproblem）：n個物品,2n實行可能解。旅行商問題（travelingsalespersonproblem）：都市n個,(n‐1)!實行可能解。

用有限時間可以求解，但計算時間太長，成本太高9012334567１2345優化技術與方法計算量(1)＋,－,×,÷比較：≠，≤，≥，＜，＞5種基本演算都是用1step

可以實現.実際上,×比＋多占用時間.「四舍五入」不算基本演算.

計算量(2)｛a1,a2,...,an｝：n個整數Q1.

求和（1）：

a1+a2+???+an.

n-1steps→O(n)算法.Q2.

求和（2）：

(1)2×a1+???+2×an,2n-1steps→O(n)算法.(2)2×(a1+???+an)

,nsteps→O(n)算法.Q3.

計算：a1b1+???+anbn.2n-1steps.Q4.2個ｎ×ｎ階矩陣相乘.

n2(2n-1)steps（n2(n+n-1)）.計算量(3)計算量(4)Q5.｛a1,a2,...,an｝：n個整數

求其和為最大的部分集合.

所有的部分集合的和進行比較2n(n-1)+(2n-1)→O(n2n)算法.計算量的膨脹(1)10行×10列棋盤上米粒的數量（第1格內放1粒米，以后每格順次增加1倍……)格序號米粒數重量(kg)112.0×10-592565.1×10-3181310722.6×10027671088641.3×10336343597383686.9×10545175921860444163.5×1085490071992547409921.8×10116346116860184273879049.2×10137223611832414348226068484.7×10168112089258196146291747061762.4×10202.4×108億噸計算量的膨脹(2)100MIPS(megainstructionspersecond)1秒間100萬回的計算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

行進300m)n101001,00010,000n10-5秒10-4秒10-3秒0.01秒n210-4秒0.01秒1秒100秒n30.001秒

1秒16.6分277時間2n0.001秒1014世紀10284世紀n!0.036秒10141世紀102551世紀宇齡：

宇宙的年齢1.5×108世紀（１５０億年）計算機速度增加的效果（1）10秒間的計算量？100MIPS10倍100倍1000倍

n1071081091010n23千1萬

3萬

10萬n3215462

1千

2千2n2327

30

33

n!101112131000倍?1step用10-9秒?

10-9秒光可以行進30cm計算機速度增加的效果（2）計算速度1秒可以求解問題的規模

O(2n)O(n)O(n2)O(n5)O(n10)100100100100100101200141115107103100031615812610710000100025115811010000031623982001131000000100006312511000001171000000031623100031610000001201000000001000001585398平行（并列）計算的場合0.5cm見方小碎片，覆蓋地球表面需要2.0×1019個.與100MIPS的單個計算機相比，能加速多少？n1001,000.2n1014世紀→0.85秒10284世紀→10263世紀n!10141世紀→10120世紀102551世紀→102530世紀問題與算法每個問題都可能有多個算法存在．每個算法的計算量（速度）都不同。例：贗品金幣問題：問題：9個外觀完全一樣的金幣.，有一個是假的（重量輕）．提問：用天秤來鑒別真偽，天秤需要使用幾次？贋品金幣問題算法使用2次天秤,就可以鑒別出假幣.789１23456左邊軽右邊軽平衡１23中有偽幣789中有偽幣456中有偽幣左邊軽１32右邊軽平衡１32456789計算量的表示法:上界值表示法O記號：(BigONotation)定義:O(f(n))讀作orderf(n),或階f(n)即：g(n)=O(f(n))表示對于任意定數c和m，以及對所有n＞m，有下式成立：g(n)＜cf(n)計算量的表示法——例n２+1000n→O(n２)logn+n3+1000n2→O(n3)判斷：n!→O(nn)？10n2→

O(n3)？logn→

O(n)？思考：O()?優化問題的規模表示優化問題大小的參數例如：旅行商問題：都市的個數;背包問題：物品的個數注：參數的個數并不僅限于1個InputSize多項式時間算法與指數時間算法指數時間算法=用問題規模的指數函數來表示計算時間的算法非有效算法的代名詞多項式時間算法=能用問題規模的多項式函數來表示計算時間的算法高效率算法的代名詞多項式時間算法的計算時間問題規模計算時間1020304050100100010000100MIPS(millioninstructionspersecond)計算機的情形指數時間算法的計算時間100MIPS(millioninstructionspersecond)計算機的情形問題規模計算時間10203040501001宙齢=150億年旅行商問題的計算量（1）n個都市訪問的可能的巡回路線：n!的Stirling近似公式BigOh記法関數的定數倍的大小可以忽略≈旅行商問題的計算量（2）根據Stirling公式以及O（）表示法O（nn）排序問題的計算量（1）：排序問題：S=｛a1,a2,...,an｝，n個整數列，按數值大小排列dataS輸入

需O(n)時間；可能的排列種類數n!種；算法中每一個比較,都增加2倍的情形數2分樹的高度（比較的次數）,

log2(n!)=O(nlog

n)x＞y?yesnon!種可能的排列排序問題計算量（2）總計算時間的復雜性：O(nlog

n)dataS輸入時間(或賦值時間)：O(n)

比較時間：O(nlog

n)上位取整計算量的確定例：背包問題的貪婪算法（greedyalgorithm）的計算量確定計算的復雜度時間復雜度：

計算量:計算各基本操作的實行回數（timecomplexity）空間復雜度各計算時點內存中保持數據個數的最大值（spacecomplexity）兩者的總稱：計算的復雜度計算復雜度的影響因素簡化模型例：RTr1/2計算復雜度的影響因素簡化模型：模型1.Lm計算復雜度的影響因素簡化模型：模型2計算復雜度的影響因素簡化模型：模型3。計算復雜度的影響因素建模假設例：高空拋球的運動軌跡。----拋物線模型假設1.沒有空氣阻力；假設2.地面是平面。----橢圓模型計算復雜度的影響因素探索空間1---解的近似度、滿意度例：0—10之間的整數解：1-9共9個可行解（一維）0—10之間的實數解：精確到小數點后6位共有107個可行解（一維）；107n個可行解（n維）探索空間2---解空間大小例：桌子上有6根火柴，要求構建出4個三角形。計算復雜度的影響因素探索策略的選取計算復雜度的影響因素問題本身P問題NP問題（NP-hard