算法分析與設(shè)計(jì)論文-背包問(wèn)題的算法設(shè)計(jì)策略對(duì)比與分析-文庫(kù)吧
2025-05-15 10:51 本頁(yè)面
【正文】 一個(gè)時(shí)候，或者找到一個(gè) i 使得 A[i]=c，或者子數(shù)組為空（即子數(shù)組下界大于上界）。前一種情況找到了等于 c 的分量，后一種情況則找不到。 這個(gè)新算法因?yàn)橛蟹磸?fù)把供查找的數(shù)組分成兩半，然后在其中一半繼續(xù)查找的特征，我們稱(chēng)為二分查找算法。它可以用函數(shù) B_Search 來(lái)表達(dá)： Function B_Search ( c: integer):integer。 Var L,U,I： integer。{U 和 L 分別是要查找的數(shù)組的下標(biāo)的上界和下界 } Found： boolean。 Begin L:=1。 U:=m。 {初始化數(shù)組下標(biāo)的上下界 } Found:=false。 {當(dāng)前要查找的范圍是 A[L]..A[U]。 } {當(dāng)?shù)扔?c 的分量還沒(méi)有找到且 U=L 時(shí)，繼續(xù)查找 } While (not Found) and (U=L) do Begin I:=(U+L) div 2。{找數(shù)組的中間分量 } If c=A[I] then Found:=Ture else if cA[I] then L:=I+1 else U:=I1。 End。 If Found then B_Search:=1 else B_Search:=0。 End。 容易理解，在最壞的情況下最多只要測(cè) A 中的 k+1(k=logm,這里的 log 以 2為底，下同 )個(gè)分量，就判斷 c 是否在 A 中。 算法 Search 和 B_Search 解決的是同一個(gè)問(wèn)題，但在最壞的情況下（所給定的 c 不在 A 中），兩個(gè)算法所需要檢測(cè)的分量個(gè)數(shù)卻大不相同，前者要 m=2 k個(gè)，后者只要 k+1 個(gè)。可見(jiàn)算法 B_Search 比算法 Search 高效得多。 以上例子說(shuō)明：解同一 個(gè)問(wèn)題，算法不同，則計(jì)算的工作量也不同，所需的計(jì)算時(shí)間隨之不同，即復(fù)雜性不同。 上圖是運(yùn)行這兩種算法的時(shí)間曲線。該圖表明，當(dāng) m 適當(dāng)大（ mm0）時(shí)，算法 B_Search 比算法 Search 省時(shí)，而且當(dāng) m 更大時(shí)，節(jié)省的時(shí)間急劇增加。 不過(guò)，應(yīng)該指出：用實(shí)例的運(yùn)行時(shí)間來(lái)度量算法的時(shí)間復(fù)雜性并不合適，因?yàn)檫@個(gè)實(shí)例時(shí)間與運(yùn)行該算法的實(shí)際計(jì)算機(jī)性能有關(guān)。換句話(huà)說(shuō)，這個(gè)實(shí)例時(shí)間不單純反映算法的效率而是反映包括運(yùn)行該算法的計(jì)算機(jī)在內(nèi)的綜合效率。我們引入算法復(fù)雜性的概念是為了比較解決同一個(gè)問(wèn)題的不同算法的效率，而不想去比較運(yùn) 行該算法的計(jì)算機(jī)的性能。因而，不應(yīng)該取算法運(yùn)行的實(shí)例時(shí)間作為算法復(fù)雜性的尺度。我們希望，盡量單純地反映作為算法精髓的計(jì)算方法本身的效率，而且在不實(shí)際運(yùn)行該算法的情況下就能分析出它所需要的時(shí)間和空間。 復(fù)雜性的計(jì)量 算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要的時(shí)間資源的量稱(chēng)作時(shí)間復(fù)雜性，需要的空間（即存儲(chǔ)器）資源的量稱(chēng)作空間復(fù)雜性。這個(gè)量應(yīng)該集中反映算法中所采用的方法的效率，而從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來(lái)。換句話(huà)說(shuō)，這個(gè)量應(yīng)該是只依賴(lài)于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如 果分別用 N、 I 和 A 來(lái)表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，用 C 表示算法的復(fù)雜性，那么應(yīng)該有： C =F(N,I,A) 其中 F(N,I,A)是 N,I,A 的一個(gè)確定的三元函數(shù)。如果把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用 T 和 S 來(lái)表示，那么應(yīng)該有： T =T(N,I,A) () 和 S =S(N,I,A) () 通常，我們讓 A 隱含在復(fù)雜性函數(shù)名當(dāng)中，因而將（ ）和（ ）分別簡(jiǎn)寫(xiě)為 T =T(N,I) 和 S =S(N,I) 由于時(shí)間復(fù)雜性和空間復(fù)雜性概念類(lèi)同，計(jì)算方法相似，且空間復(fù)雜性分 析相對(duì)地簡(jiǎn)單些，所以下文將主要地討論時(shí)間復(fù)雜性。 下面以 T(N,I)為例，將復(fù)雜性函數(shù)具體化。 根據(jù) T(N,I)的概念，它應(yīng)該是算法在一臺(tái)抽象的計(jì)算機(jī)上運(yùn)行所需的時(shí)間。設(shè)此抽象的計(jì)算機(jī)所提供的元運(yùn)算有 k 種，他們分別記為 O1,O2 ,..,Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時(shí)間分別為 t1,t2,..,tk 。對(duì)于給定的算法 A，設(shè)經(jīng)過(guò)統(tǒng)計(jì)，用到元運(yùn)算 Oi 的次數(shù)為 ei， i=1,2,..,k ，很明顯，對(duì)于每一個(gè) i， 1=i=k， ei 是 N 和 I 的函數(shù)，即 ei=ei(N,I)。那么有： () 其中 ti， i=1,2,..,k,是與 N,I 無(wú)關(guān)的常數(shù)。 顯然，我們不可能對(duì)規(guī)模 N 的每一種合法的輸入 I 都去統(tǒng)計(jì) ei(N,I),i=1,2,…,k。因此 T(N,I)的表達(dá)式還得進(jìn)一步簡(jiǎn)化，或者說(shuō)，我們只能在規(guī)模為 N 的某些或某類(lèi)有代表性的合法輸入中統(tǒng)計(jì)相應(yīng)的 ei , i=1,2,…,k ，評(píng)價(jià)時(shí)間復(fù)雜性。 下面只考慮三種 情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，并分別記為 Tmax(N )、 Tmin(N)和 Tavg(N )。在數(shù)學(xué)上有： () () () 其中， DN 是規(guī)模為 N 的合法輸入的集合； I *是 DN 中一個(gè)使 T(N,I *)達(dá)到Tmax(N)的合法輸入，
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1