第2章第1節(jié)下界的算法

第2章WPF完全理論2.1下界對(duì)于任何待求解的問(wèn)題，如果能找到一個(gè)盡可能大的函數(shù)g(n)（n為問(wèn)題規(guī)模），使得求解該問(wèn)題的所有算法都可以在Ω(g(n))的時(shí)間內(nèi)完成，則函數(shù)g(n)稱(chēng)為該問(wèn)題計(jì)算復(fù)雜性的下界（LowerBound）。如果已經(jīng)知道一個(gè)和下界的效率類(lèi)型相同的算法，則稱(chēng)該下界是緊密（Close）的。意義：評(píng)價(jià)算法；改進(jìn)算法。2.1.1平凡下界對(duì)問(wèn)題的輸入中必須要處理的元素進(jìn)行計(jì)數(shù)，同時(shí)，對(duì)必須要輸出的元素進(jìn)行計(jì)數(shù)。這種計(jì)數(shù)方法產(chǎn)生的是一個(gè)平凡下界（OrdinaryLowerBound）.例：生成n個(gè)元素的所有排列對(duì)象的算法屬于Ω(n!)平凡下界往往過(guò)小而失去意義。例：TSP問(wèn)題的平凡下界是Ω(n2)2.1.2判定樹(shù)模型判定樹(shù)（DecisionTrees）是這樣一棵二叉樹(shù)：它的每一個(gè)內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)一個(gè)形如x≤y的比較，如果關(guān)系成立，則控制轉(zhuǎn)移到該結(jié)點(diǎn)的左子樹(shù)，否則，控制轉(zhuǎn)移到該結(jié)點(diǎn)的右子樹(shù)，它的每一個(gè)葉子結(jié)點(diǎn)表示問(wèn)題的一個(gè)結(jié)果。在用判定樹(shù)模型建立問(wèn)題的時(shí)間下界時(shí)，通常忽略求解問(wèn)題的所有算術(shù)運(yùn)算，只考慮分支執(zhí)行時(shí)的轉(zhuǎn)移次數(shù)。引理2.1若T是至少具有n！和葉子結(jié)點(diǎn)的二叉樹(shù)，則T的高度至少是：nlog2n-1.5n=Ω(nlog2n)通常稱(chēng)為信息論下界，說(shuō)明任何基于比較的對(duì)n個(gè)元素排序的算法，判定樹(shù)的高度都不會(huì)大于Ω(nlog2n)。因此，Ω(nlog2n)是這些算法的時(shí)間下界。定理2.1任何基于比較的排序算法，對(duì)n個(gè)元素進(jìn)行排序的時(shí)間下界為Ω(nlog2n)例：對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹(shù)a1<a2a1<a2a1<a2<a3是是是否否否a1<a3a2<a3a2<a1<a3a2<a3a3<a2<a1a2<a3<a1a1<a3a3<a1<a2a1<a3<a2否否是是最壞情況下的時(shí)間復(fù)雜性是從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，它不會(huì)超過(guò)判定樹(shù)的高度。2.1.3最優(yōu)算法所謂最優(yōu)算法（OptimalityAlgorithm）是指在某一種度量標(biāo)準(zhǔn)下，優(yōu)于該問(wèn)題的所有（可能的）算法。如果能夠證明求解問(wèn)題Π的任何算法的運(yùn)行時(shí)間下界是Ω(g(n))，那么，對(duì)以時(shí)間O(g(n))來(lái)求解問(wèn)題Π的任何算法，都認(rèn)為是最優(yōu)算法。例：求數(shù)組最小值算法intArrayMin(inta[],intn)min=a[0];for(i=1;i<n;i++)if(a[i]<min)min=a[i];returnmin;實(shí)際上是將元素從集合A向集合B和集合C移動(dòng)的過(guò)程，但每次比較至多能把一