算法和算法分析
Algorithms and Algorithm Analysis
算法
所謂算法(Algorithm)是對問題求解步驟的一種描述是指令的有限序列其中每一條指令表示一個或多個操作在CLRS中是這樣給出算法的定義的Informally an algorithm is any welldefined computational procedure that takes some value or set of values as input and produces some value or set of values as output An algorithm is thus a sequence of computational steps that transform the input into the output
一個算法必須滿足以下五個重要特性
有窮性 對於任意一組合法輸入值在執行有窮步驟之後一定能結束即算法中的每個步驟都能在有限時間內完成;
確定性 對於每種情況下所應執行的操作在算法中都有確切的規定使算法的執行者或閱讀者都能明確其含義及如何執行並且在任何條件下算法都只有一條執行路徑;
可行性 算法中描述的操作都可以通過已經實現的基本操作運算有限次實現之;
有輸入 作為算法加工對象的量值通常體現為算法中的一組變量有些輸入量需要在算法執行過程中輸入而有的算法表面上可以沒有輸入實際上已被嵌入算法之中;
有輸出 它是一組與輸入有確定關系的量值是算法進行信息加工後得到的結果
算法設計的原則
設計算法時我們應當嚴格考慮
正確性(Correctness)
首先算法應當滿足以特定的規格說明方式給出的需求對算法是否正確的理解可以有以下四個層次
a程序中不含語法錯誤;
b程序對於幾組輸入數據能夠得出滿足要求的輸出結果;
c程序對於精心選擇的典型苛刻的幾組輸入數據能夠得出滿足要求的結果;
d程序對於一切合法的輸入數據都能得出滿足要求的結果;
通常以第c層意義的正確性作為衡量一個算法是否合格的標准因為作為輸入我們有時候不可能提前做出所有的預期
可讀性(Readability)
算法主要是為了人的閱讀與交流其次才是為計算機執行因此算法應該易於人的理解;另一方面晦澀難讀的程序易於隱藏較多錯誤而難以調試;有些程序設計者總是把自己設計的算法寫的只有自己才能看懂這樣的算法反而沒有太大的價值
健壯性(Rubustness)
當輸入的數據非法時算法應當恰當地作出反映或進行相應處理而不是產生莫名奇妙的輸出結果這就需要我們一定要充分的考慮異常情況(Unexpected Exceptions)並且處理出錯的方法不應是中斷程序的執行而應是返回一個表示錯誤或錯誤性質的值以便在更高的抽象層次上進行處理
高效率與低存儲量需求
通常效率指的是算法執行時間;存儲量指的是算法執行過程中所需的最大存儲空間兩者都與問題的規模有關
算法效率的衡量方法與准則
通常有兩種衡量算法效率的方法:
事後統計法
缺點
()必須執行程序才能進行判斷
()其它因素(如硬件軟件環境)掩蓋算法本質
事前分析估算法
主要是看消耗的時間和算法執行時間相關的因素
算法選用的策略
問題的規模
編寫程序的語言
編譯程序產生的機器代碼的質量
計算機執行指令的速度
一個特定算法的運行工作量的大小只依賴於問題的規模(通常用整數量n表示)或者說它是問題規模的函數假如隨著問題規模n的增長算法執行時間的增長率和f(n)的增長率相同則可記作
T (n) = O(f(n))
稱T (n) 為算法的漸近時間復雜度(Asymptotic Time Complexity)簡稱時間復雜度O是數量級的符號
下面我們探討一下如何估算算法的時間復雜度
算法 = 控制結構 + 原操作(固有數據類型的操作)
算法的執行時間=原操作(i)的執行次數×原操作(i)的執行時間
算法的執行時間與原操作執行次數之和成正比
我們先介紹一個概念
for(j=;j <=n;++j)
for(k=;k <=n;++k){++x;x+=x;}
語句重復執行的次數被稱為語句的頻度(Frequency Count)上程序段中++x的語句頻度就是n
我們經常采用從算法中選取一種對於所研究的問題來說是基本操作的原操作以該基本操作在算法中重復執行的次數作為算法運行時間的衡量准則這個原操作多數情況下是最深層次循環內的語句中的原操作
例如
for (i=; i <=n; ++i)
for (j=; j <=n; ++j) {
c[ij] = ;
for (k=; k <=n; ++k)
c[ij] += a[ik]*b[kj];
}
該算法的基本操作是乘法操作時間復雜度為 O(n)
算法的存儲空間(Memory Space for Algorithms)
算法的空間復雜度S(n) = O(g(n))
表示隨著問題規模n的增大算法運行所需存儲量的增長率與g(n)的增長率相同
算法的存儲量包括:
輸入數據所占空間;
程序本身所占空間;
輔助變量所占空間
若輸入數據所占空間只取決與問題本身和算法無關則只需要分析除輸入和程序之外的額外空間若所需額外空間相對於輸入數據量來說是常數則稱此算法為原地工作
[] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23997.html
