資訊科學是探討演算法則與資料結構的科學,使用最適當的資料結構,才能夠設計出最有效率的演算法則
資料結構:探討一群相關資料的資料表示方法與資料運作方法
ADT(abstract data type,抽象化資料型態)：一種資料型態,必需滿足包裝與資訊隱藏兩個條件
包裝:資料表示方法和運算方法,需在一特殊的程式單元內宣告與描述,目地:讓之後的修改能在此特殊的程式單元中進行
資訊隱藏:包裝需隱藏,不可讓使用抽象化資料型態的程式得知,目地:讓程式不需隨著抽象化型態內部表示方式改變而修改
資料的邏輯關係分為：
線性關性(存在先後順序)
階層關係(資料有上下階層，存在包含關係)
相鄰關係(資料互連)
資料表示法分為:
循序表示法(陣列):資料邏輯順序與儲存在記憶體的實際順序相同
鏈結表示法(鏈結串列):資料邏輯順序與與存在記憶體的實際順序不同
常見的資料型態有:
陣列型態
結構型態
指標型態
……………………………………………………
演算法需具備
output(輸出性):至少要產生一個結果
definitieness(明確性):各步驟描述須十分明確(描述工具有自然語言,程式語言,流程圖,虛擬碼)
effectiveness(有限性):需在有限步驟內結束
finiteness(有效性):各步驟可被執行,具可行性,且不可或缺
演算法則的基本步驟:
sequence(循序步驟)
selection(選擇步驟)
iteration(重覆步驟)
………………..
複雜度符號:
big omega:
lower bound複雜度下限(最佳情況),分析演算法是否己最佳化
若f(N)=big omega(g(N))成立時,則存在2個常數C,N0,使得|f(N)|>=C|g(N)|,當N>=N0
omega
big omega去掉theta部份
big O:
upper bound複雜度上限(最差情況),忽略常數只取最高次方項即可得
若f(N)=big O(g(N))成立時,則存在2個存數C,N0,使得|f(N)|<=C|g(N)|,當N>=N0
ex:f(n)=n^m+a1n+a0的時間複雜度=O(n^m)
ex:f(n)=n(n-1)/2=(n^2-n)/2=(n^2)*1/2-n/2,n^2為最高次方項,時間複雜度為O=(n^2)
o
big O去掉theta部份
theta:
複雜度上限和複雜度下限一樣時,ex:theada(N)=big O(N)和big omega(N)
若f(N)=theada(g(N))成立時,則存在三個常數C1,C2,N0,使得C1|g(N)|<=|f(N)|<=C2|g(N)|,當N>=N0
ps:
當時間複雜度正好與這個問題的時間複雜度下限相同時,也稱為asymptotically optimal algorithm
ps:
除非資料數n夠大,否則複雜度等級小不一定有效率
ps:
複雜度符號也被稱為asymptotic notations(近似符號)
複雜度等級:
多項式演算法則(多項式複雜度):可行的演算法則
(1):常數複雜度，所需時間永遠固定,ex雜湊表
(2底log n):對複複雜度，時間和資料量成對數關係,ex二分搜尋,二元樹搜尋,費式搜尋
(n);線性複雜度,ex:循序搜尋,二元樹走訪
(n 2底log n):次線性複雜度,ex:快速排列法，二項合併排序法，堆積排序法
(n^2):平方複雜度，時間和資料量成平方關係,ex:矩陣加減,簡單排序演算法,插入排序法,選擇排序法,氣泡排序法
(n^3):立方複雜度，ex:兩個n*n矩陣相乘
指數演算法則(指數複雜度)：不可行的演算法則
(2^n):指數複雜度，ex:部份集合之問題,河內塔問題,排列問題
(n!):
複雜度計算
theta
1+1+….+1=n=theta(n):通常是一個迴圈
1+2+……+n=n(n+1)/2=theta(n^2)
1^2+2^2+…..+n^2=n(n+1)(2n+1)/6=theta(n^3)
1^k+2^k+…..+n^k=theta(n^(k+1))
1+1/2+1/3+… + 1/n =theta(lg n)
1+r+r^2+r^3+…+ r^n= (r^(n+1)-1)/(r-1) =theta(r^n)
bigO
1+2+3+…n < n+n+…n = n^2 = bigO(n^2)
n!=1*2*3*…*n < n*n*…*n = n^n = bigO(n^n)
n*log(n)! = bigO(n*log(n))
兩函數相加的複雜度等級判斷
原則:展開範圍後,在取最大
ex:
bigO(n)+bigO(n*log(n))
bigO(n)=[1,n]
bigO(n*log(n))=[1,n*log(n)]
取最大得到[1,n*log(n)],屬於bigO(n*log(n))
ex:
big_omega(n)+theta(n^2)
big_omega(n)=[n,infinite]
big_theta(n^2)=[n^2,n^2]
取最大得到[n^2,infinite],屬於big_omega(n^2)
ex:
theta(n)+bigO(n^2)
theta(n)=[n,n]
bigO=[1,n^2]
取最大得到[n,n^2],屬於big_omega(n) and bigO(n^2)
…………………
問題的分類
不可計算的問題：不存在有解決問題的演算法
部份可計算的問題：不存在解決問題的演算法，在部份情況下可得到結果
可計算的問題：有解決問題的演算法，含可行與不可行
n,np問題
p問題:
可用決定性演算法(一般的)解決,屬於np問題(因決定性演算法可視為非決定性演算法之特例)
np問題:
可用非決定性演算法(可把複雜p問題變容易)在多項式時間內解決的問題,
尚未找到多項式複雜度的決定性演算法的np問題有：漢彌敦迴路問題，旅行推銷員問題，最大完整子圖問題
np-complete理論利用問題間的歸納關係將問題分成：
np-hard問題
np-complete問題:所有np-complete問題,都屬於np-hard問題 ,ex:旅行推銷員
np-hard問題:
如果問題l屬於[np-hard問題]，若且為若[滿足問題]可歸納為問題l(表示為sat可歸納為l)
指一群複雜度等級不小於’滿足問題’的問題，屬於np問題
np-complete問題:
如果問題L是屬於[np-complete問題]，若且為若問題L是屬於[np-hard問題]，同時問題L也是屬於[np問題]
所有np-complete問題都是相關的，都須符合下列條件：
如果可有一個[np-complet問題]能夠找到多項式複雜度的[決定性的演算法則]，若且為若所有[np-complete問題]也都存在多項式複雜度的[決定性演算法則]
np-complete問題與np-hard問題之間也存在下列關係：
如果有一個[np-hard問題]能夠找到多項式複雜度的[決定性的演算法則]，則所有[np-complete問題]也都存在多項式複雜度的[決定性的演算法則]