一、什么是算法？

　　算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜度與時間復雜度來衡量。

　　算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出并停止于一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在內的一些算法，包含了一些隨機輸入。

　　二、算法的特征

　　有窮性（Finiteness）

　　算法的有窮性是指算法必須能在執行有限個步驟之后終止；

　　確切性（Definiteness）

　　算法的每一步驟必須有確切的定義；

　　輸入項（Input）

　　一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；

　　輸出項（Output）

　　一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的；

　　可行性（Effectiveness）

　　算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

　　三、算法的要素

　　1、數據對象的運算和操作

　　計算機可以執行的基本操作是以指令的形式描述的。一個計算機系統能執行的所有指令的集合，成為該計算機系統的指令系統。一個計算機的基本運算和操作有如下四類：

　　1）算術運算：加減乘除等運算

　　2）邏輯運算：或、且、非等運算

　　3）關系運算：大于、小于、等于、不等于等運算

　　4）數據傳輸：輸入、輸出、賦值等運算

　　2、算法的控制結構

　　一個算法的功能結構不僅取決于所選用的操作，而且還與各操作之間的執行順序有關。

　　四、五大常用算法

　　1、分治算法

　　1）基本概念

　　在計算機科學中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法（快速排序，歸并排序），傅立葉變換（快速傅立葉變換）……

　　任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

　　2）基本思想及策略

　　分治法的設計思想是：將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

　　分治策略是：對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。

　　如果原問題可分割成k個子問題，1《k≤n，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。

　　3）分治法適用的情況

　　分治法所能解決的問題一般具有以下幾個特征：

　　1） 該問題的規模縮小到一定的程度就可以容易地解決

　　2） 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。

　　3） 利用該問題分解出的子問題的解可以合并為該問題的解；

　　4） 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

　　第一條特征是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；

　　第二條特征是應用分治法的前提它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用；、

　　第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態規劃法。

　　第四條特征涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。

　　4）分治法的基本步驟

　　分治法在每一層遞歸上都有三個步驟：

　　step1 分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；

　　step2 解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題

　　step3 合并：將各個子問題的解合并為原問題的解。

　　它的一般的算法設計模式如下：

　　Divide-and-Conquer（P）

　　1. if |P|≤n0

　　2. then return（ADHOC（P））

　　3. 將P分解為較小的子問題 P1 ，P2 ，。。。，Pk

　　4. for i←1 to k

　　5. do yi ← Divide-and-Conquer（Pi） △ 遞歸解決Pi

　　6. T ← MERGE（y1，y2，。。。，yk） △ 合并子問題

　　7. return（T）

　　其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規模的問題P。因此，當P的規模不超過n0時直接用算法ADHOC（P）求解。算法MERGE（y1，y2，。。。，yk）是該分治法中的合并子算法，用于將P的子問題P1 ，P2 ，。。。，Pk的相應的解y1，y2，。。。，yk合并為P的解。