演算法：分析基礎

一、演算法的特徵

（1）可行性：

（2）確定性：

（3）有窮性：

（4）輸入：

（5）輸出：

二、演算法的評價

1.正確性

2.可讀性

3.健壯性

4.複雜性

概要地描述一個分析演算法效率的一般性框架.首先必須指出,有兩種演算法效率:時間效率和空間效率。

時間效率指出正在討論的演算法運行得有多快；

空間效率關心演算法需要的額外空間。

運行時間的度量單位

A. 把基本操作作為演算法運行時間的度量單位。

所謂基本操作，就是演算法中最重要的操作。它們對總運行時間的貢獻最大。

B. 計算基本操作的運行次數。

掌握了這樣一種規律，就不難發現一個演算法中的基本操作：它通常是演算法最內層循環中最費時的操作。例如，大多數排序演算法是通過比較列表中的待排序元素（鍵）來進行工作的；對於這種演算法來說，基本操作就是對鍵的比較。

三、演算法的增長次數

四、演算法的最優、最差和平均效率

一個演算法的最差效率是指當輸入規模為n時，演算法在最壞情況下的效率。。

一個演算法的最優效率是指當輸入規模為n時，演算法在最優情況下的效率。

無論是最差效率分析還是最優效率分析都不能提供一種必要的信息：在「典型」或者「隨機」輸入的情況下， 一個演算法會具有什麼樣的行為。這正是平均效率試圖提供給我們信息。

攤銷效率: 它並不適用於演算法的單次運行，而是應用於演算法對同樣數據結構所執行的一系列操作。

五、漸進符號和基本效率類型

O(g(n)) 是增長次數小於等於g(n) (以及其常數倍，n趨向於無窮大)的函數集合。

n∈O(n2),100n+5∈O(n2), n(n-1) /2 ∈O(n2),n3∈/ O(n2),

存在大於0的常數c和非負的整數n0，使得：對於所有的n≥ n0來說， t(n) ≤c g(n)

Ω(g(n))，代表增長次數大於等於g(n)(以及其常數倍,n趨向於無窮大)的函數集合。

n3∈ Ω(n2)， n(n-1) /2 ∈ Ω(n2)，但是100n+5 ∈/ Ω(n2)

存在大於0的常數c和非負的整數n0，使得：對於所有的n≥ n0來說， t(n) ≥c g(n)

Θ(g(n))是增長次數等於g(n) )(以及其常數倍,n趨向於無窮大)的函數集合。因此，每一個二次方程an2+bn+c在a>0的情況下都包含在Θ(n2)中

存在大於0的常數c1，c2和和非負的整數n0，使得：對於所有的n≥ n0來說， c2g(n) ≤t(n) ≤ c1g(n)

六、1.漸進符號的有用特性—加法規則

定理：如果t1(n) ∈O(g1(n))並且t2(n) ∈O(g2(n))，則

t1(n)+ t2(n)∈O(max{g1(n), g2(n)})

(對於Ω和Θ符號， 類似的斷言也為真)

對於兩個連續執行部分組成的演算法，應該如何應用這個特性呢？它意味著該演算法的整體效率是由具有較大的增長次數的部分所決定的，即它的效率較差的部分.

2.漸進符號的有用特性—乘法規則

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！