第一講：計(jì)算復(fù)雜性理論

第一講：計(jì)算復(fù)雜性理論

(ComplexityTheory)

計(jì)算量的概念計(jì)算量的表示算法與計(jì)算量計(jì)算復(fù)雜性影響計(jì)算復(fù)雜性的因素

優(yōu)化問(wèn)題及其計(jì)算的復(fù)雜性

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

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

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

計(jì)算量(2)｛a1,a2,...,an｝：n個(gè)整數(shù)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.

計(jì)算：a1b1+???+anbn.2n-1steps.Q4.2個(gè)ｎ×ｎ階矩陣相乘.

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

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

所有的部分集合的和進(jìn)行比較2n(n-1)+(2n-1)→O(n2n)算法.計(jì)算量的膨脹(1)10行×10列棋盤上米粒的數(shù)量（第1格內(nèi)放1粒米，以后每格順次增加1倍……)格序號(hào)米粒數(shù)重量(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億噸計(jì)算量的膨脹(2)100MIPS(megainstructionspersecond)1秒間100萬(wàn)回的計(jì)算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

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

1秒16.6分277時(shí)間2n0.001秒1014世紀(jì)10284世紀(jì)n!0.036秒10141世紀(jì)102551世紀(jì)宇齡：

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

n1071081091010n23千1萬(wàn)

3萬(wàn)

10萬(wàn)n3215462

1千

2千2n2327

30

33

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

10-9秒光可以行進(jìn)30cm計(jì)算機(jī)速度增加的效果（2）計(jì)算速度1秒可以求解問(wèn)題的規(guī)模

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

O(n3)？logn→

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

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

log2(n!)=O(nlog

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

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

比較時(shí)間：O(nlog

n)上位取整計(jì)算量的確定例：背包問(wèn)題的貪婪算法（greedyalgorithm）的計(jì)算量確定計(jì)算的復(fù)雜度時(shí)間復(fù)雜度：

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