0.算法設計與分析__緒論

算法及其重要特性

算法（Algorithm）：對特定問題求解步驟的一種描述，是指令的有限序列。

算法的五大特性：

⑴ 輸入：一個算法有零個或多個輸入。

⑵ 輸出：一個算法有一個或多個輸出。

⑶ 有窮性：一個算法必須總是在執行有窮步之後結束，且每一步都在有窮時間内完成。

⑷ 确定性：算法中的每一條指令必須有确切的含義，對于相同的輸入隻能得到相同的輸出。

⑸ 可行性：算法描述的操作可以通過已經實作的基本操作執行有限次來實作。

問題的求解過程：

分析問題→設計算法→編寫程式→整理結果

算法（Algorithm）：對特定問題求解步驟的一種描述，是指令的有限序列。

例子： ​​歐幾裡德算法——輾轉相除法求兩個自然數 m 和 n 的最大公約數​​

算法設計的一般過程

1．了解問題

2．預測所有可能的輸入

3. 在精确解和近似解間做選擇

4. 确定适當的資料結構

5．算法設計技術

6．描述算法

7．跟蹤算法

8．分析算法的效率

9．根據算法編寫代碼

算法分析

算法分析（Algorithm Analysis）：對算法所需要的兩種計算機資源——時間和空間進行估算

時間複雜性（Time Complexity）

空間複雜性（Space Complexity）

算法分析的目的：

設計算法——設計出複雜性盡可能低的算法

選擇算法——在多種算法中選擇其中複雜性最低者

時間複雜性分析的關鍵：

問題規模：輸入量的多少；

基本語句：執行次數與整個算法的執行時間

成正比的語句

漸進符号

1. 大O符号

   定義1.1 若存在兩個正的常數c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))，或稱算法在O(f(n)中。

2. 大Ω符号

   定義1.2 若存在兩個正的常數c和n0，對于任意n≥n0，都有T(n)≥c×g(n)，則稱T(n)=Ω(g(n))

3. Θ符号

   定義1.3 若存在三個正的常數c1、c2和n0，對于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，則稱T(n)=Θ(f(n))

最好、最壞和平均情況

結論：如果問題規模相同，時間代價與輸入資料有關，則需要分析最好情況、最壞情況、平均情況。

最好情況：出現機率較大時分析

最差情況：實時系統

平均情況：已知輸入資料是如何分布的，

通常假設等機率分布

非遞歸算法的分析

1. 決定用哪個（或哪些）參數作為算法問題規模的度量
2. 找出算法中的基本語句
3. 檢查基本語句的執行次數是否隻依賴于問題規模
4. 建立基本語句執行次數的求和表達式
5. 用漸進符号表示這個求和表達式