【文章內(nèi)容簡介】 是 DN 中一個使 T(N, )到 Tmin(N)的合法輸入；而 P(I)是在算法的應(yīng)用中出現(xiàn)輸入 I 的概率。 以上三種情況下的時間復(fù)雜性各從某一個角度來反映算法的效率，各有各的用處，也各有各的局限性。但實踐 表明可操作性最好的且最有實際價值的是最壞情況下的時間復(fù)雜性。下面我們將把對時間復(fù)雜性分析的主要興趣放在這種情形上。 一般來說，最好情況和最壞情況的時間復(fù)雜性是很難計量的，原因是對于問題的任意確定的規(guī)模 N 達到了 Tmax(N)的合法輸入難以確定，而規(guī)模 N 的每一個輸入的概率也難以預(yù)測或確定。我們有時也按平均情況計量時間復(fù)雜性，但那時在對 P(I)做了一些人為的假設(shè)（比如等概率）之后才進行的。所做的假設(shè)是否符合實際總是缺乏根據(jù)。因此，在最好情況和平均情況下的時間復(fù)雜性分析還僅僅是停留在理論上。 2 常見的算法分析設(shè)計 策略介紹 我們一般常見的幾種算法分析設(shè)計策略主要有：動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法。接下來我主要介紹一下這幾種算法。 動態(tài)規(guī)劃 動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計算那樣，具有一個標(biāo)準的數(shù)學(xué)表達式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此 讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論，逐漸學(xué)會并掌握這一設(shè)計方法。 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的 問題，經(jīng)分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。 在編程中常用解決最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線等 問題。 貪心算法 所謂貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。 貪心算法的基本思路 ： 。 。 c..對每一子問題求解，得到子問題的局部最優(yōu)解。 d..把子問題的解局部最優(yōu)解合成原來解問題的一個解。 實現(xiàn)該算法的過程： ； 能朝給定總目標(biāo)前進一步 do ； 。 ，貪心解的確不錯，可惜不是最優(yōu)解。 回溯法 回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回 溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。 回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié) 點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。 用回溯法解題的一般步驟： （ 1）針對所給問題，定義問題的解空間； （ 2）確定易于搜索的解空間結(jié)構(gòu)； （ 3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 分 支限界法 分支定界 (branch and bound) 搜索法是一