data structures concept

資訊科學是探討演算法則與資料結構的科學,使用最適當的資料結構,才能夠設計出最有效率的演算法則
資料結構:探討一群相關資料的資料表示方法與資料運作方法

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問題]也都存在多項式複雜度的[決定性的演算法則]


2007-03-05 18:56:12發表 2014-04-21 21:21:22修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法

Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net