封裝技術

[拼音]：suanfasheji yu fenxi

[英文]：design and analysis of algorithms

設計出高質量的演算法，並研究演算法所耗費的計算資源與問題規模之間的函式關係。演算法設計與演算法分析是不可分割的一個整體。演算法分析的物件是被設計出的演算法，而每一個被設計出的演算法只有經過演算法分析，才能評價其質量之優劣。

計算效率是一個古老的研究課題。科學技術的發展使得計算日趨複雜，計算量越來越大，許多理論上可計算的問題，常常由於其計算量巨大布變成了現實不可計算的問題，這就產生了理論可計算而現實不可計算的矛盾。20世紀60年代以來，隨著各個領域演算法研究工作的發展，產生了一個嶄新的研究領域，這就是演算法的設計與分析。在這一方面已取巨大的進展，它的研究成果對於計算機在各個領域的應用起著重要的作用。

基本內容

按照演算法所處理的物件進行分類，演算法設計與分析主要有數值演算法和非數值演算法兩大領域。數值演算法主要包括多項式計算、矩陣計算、有限域計算、數論計算等有關數值計算的演算法問題。非數值演算法主要包括整序搜尋、幾何問題的計算、離散結構的計算、模式匹配等有關非數值計算的演算法問題。

按照計算方式進行分類，則可分為序列演算法和並行演算法，還可以分為確定型演算法、非確定型演算法、交錯型演算法、隨機型演算法等（見計算複雜性理論）。

另外，還有關於近似演算法的研究。對於已經證明不存在快速演算法，或者至今還未找到快速演算法的問題，例如NP完全問題（見NP完全性），與其花費大量的時間去尋找精確解，不如花費少量的時間去尋找近似解。

基本概念

設計演算法與分析演算法的複雜度，都與計算模型有關，大多屬於隨機存取機器模型，這是一種確定型的序列計算模型。

隨機存取機器是一種理想的計算機，由一個累加器、一個儲存器和一個程式組成。儲存器具有無限多個暫存器，每個暫存器可以存放任意大的一個自然數。程式是由一些最基本的指令所組成的序列，這些指令通常是指包括直接定址與間接定址在內的加、減、乘、除、取數、存數、條件轉移和停機。所有的運算和邏輯判斷都在累加器中進行。

問題的大小，也稱問題的規模，通常用一個自然數作為隨機存取機器輸入資料量多少的度量。

時間複雜度和空間複雜度分別表示對於規模為 n的輸入問題、隨機存取機器所耗費的時間與空間，它們都是 n的函式。常用的時間和空間的度量方式是均勻耗費標準：執行一條指令算作耗費一個單位的空間，使用一個暫存器算作耗費一個單位的空間；另一種度量方式是對數耗費標準（見隨機存取機器模型）。複雜度函式的計算方式又有兩種：規模為n的所有問題的複雜度的最大值稱為最環情況複雜度；規模為n的所有問題的複雜度的平均值稱為平均情況複雜度。當規模n增加時，複雜度的量級即極限屬性稱為漸近複雜度。由於理論計算機與現實計算機之間的差異，以及不同的現實計算機之是的差異，也由於演算法設計與分析主要關心規模 n比較大的情況，通常討論的是漸近複雜度。

演算法設計

演算法設計的任務是對各類具體的問題設計高質量的演算法，以及研究設計演算法的一般規律和方法。常用的演算法設計方法主要有分治法、動態規劃、貪婪法和回溯法等。

分治法

把一個大規模問題劃分成幾個子問題，對每一個子問題採用同樣的處理方法，求出各子問題的解答，再把這些子問題的解答組合成整個問題的解答。

動態規劃

當整個問題的解答無法由少數幾個子問題的解答組合得出，而依賴於大量子問題的解答，並且子問題的解答又需要反覆利用多次時，系統地列表記錄各個子問題的解答，據此求出整個問題的解答。

貪婪法

在演算法的每一步驟，都採取當前看來可行的或最優的策略。這是一種最直接的方法，只有在一些特殊情況下，貪婪法才能求出問題的解答。對於錄求最優解的問題、貪婪法通常只能求出近似解。

回溯法和分叉截斷法

為了尋求問題的解答，有時需要在所有的可能性(稱為候選物件)中進行系統的搜尋，例如在尋求最優解的問題中，就常碰到這種情況。這時，須把各種候選物件組織成一棵樹，每個樹葉對應著一個候選物件，於是每個內部頂點就表示若干個候選物件(即在此頂點下面的樹葉)。回溯法是從樹根開始按深度優先搜尋的原則向下搜尋，即沿著一個方向儘量向下搜尋，直到發現此方向上不可能存在解答時，就退到上一個頂點，沿另一個方向進行同樣的工作。分叉截斷法也是從樹根開始向下搜尋，不同的是，分叉截斷法常常利用一個適當選取的評估函式，來決定應該從哪一點開始下一步搜尋（分叉），以及哪一點下方不可能存在解答，從而這點的下方不必進行搜尋（截斷）。評估函式選得好，就會很快地找到解答，選得不好，就可能找不到解答或者找到的不是最優解（有時它可以作為最優解的一個近似解）。