本章內(nèi)容:算法的定義,特性,算法設(shè)計的要求,算法效率的度量方法,算法時間復(fù)雜度,算法空間復(fù)雜度
一.算法基礎(chǔ)
1.定義
算法是解決特定問題求解步驟的描述,在計算機中表現(xiàn)為指令的有限序列,并且每條指令表示一個或多個操作
2.特性
1.輸入輸出
算法具有零個或多個輸入,至少具有一個或多個輸出
2.有窮形
算法不會無限循環(huán),并且每個步驟在可接受的時間內(nèi)完成
3.確定性
每一步驟都有確定含義,不會出現(xiàn)二義性
4.可行性
每一步驟必須可行,即每一步都能通過執(zhí)行有限次數(shù)完成
3.設(shè)計要求
1.正確性
算法至少應(yīng)該具有輸入,輸出,加工處理無歧義性,能正確反映問題的需求,能夠得到問題的答案
2.可讀性
算法設(shè)計的另一目的是為了便于閱讀,理解和交流
3.健壯性
當(dāng)輸入數(shù)據(jù)不合法時,算法也能做出相關(guān)處理,而不是產(chǎn)生異常結(jié)果
4.時間效率高,存儲量低
時間效率指算法的執(zhí)行時間,存儲量需求指的是算法在執(zhí)行過程中需要的最大存儲空間,主要指算法在程序運行時所占用的內(nèi)存或外部硬盤存儲時間
二.算法效率的度量方法
1.事后統(tǒng)計方法
缺陷較多,不予考慮
2.事前分析估算方法
程序的運行時間,依賴于算法的好壞,和問題的輸入規(guī)模
三.算法時間復(fù)雜度
1.定義
在進行算法分析時,語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù),進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級.算法的時間復(fù)雜度,也就是算法的時間量度,記做:T(n) = O(f(n)).它表示隨問題規(guī)模n的增大,算法執(zhí)行時間的增長率和f(n)的增長率相同,稱作算法的漸進時間復(fù)雜度,簡稱為時間復(fù)雜度,其中f(n)是問題規(guī)模n的某個函數(shù).
2.推導(dǎo)大O階方法
1.用常數(shù)1取代運行時間中的所有加法常數(shù)
2.在修改后的運行次數(shù)函數(shù)中,只保留最高階項
3.如果最高項存在且不是1,則去除與這個項相乘的常數(shù)
3.常見的時間復(fù)雜度
1.常數(shù)階
2.線性階
3.對數(shù)階
4.平方階
5.常見時間復(fù)雜度比較
四.算法空間復(fù)雜度
通過計算算法所需的存儲空間實現(xiàn),算法空間復(fù)雜度的計算公式記做S(n) = O(f(n)).n為問題的規(guī)模,f(n)
是語句關(guān)于n所占存儲空間的函數(shù)
五.總結(jié)
