資料結構的簡介

程式設計就是資料結構與演算法結合起來，撰寫程式前先規劃所需的資料結構，資料結構就會影響程式的演算法，利用演算法操作資料結構，完成預訂所需要達成的功能，以下介紹資料結構、演算法、演算法複雜度、程式執行效率等。

1-1資料結構的定義

資料結構(Data Structure)為電腦儲存與操作資料的方式，包含儲存的容器、新增資料、讀取資料、刪除資料與搜尋資料等。例如：要建立一個電話簿功能的程式，就要考慮合適的資料結構，該結構要能夠新增電話號碼與聯絡人，能夠依照聯絡人搜尋電話號碼，能夠刪除聯絡人與電話號碼，就可以選用陣列(Array)、鏈結串列(Linked List)或字典(dict)等資料儲存容器製作抽象資料型別，每一種資料儲存容器都有其特性，在之後章節會介紹。

日常生活中所遇到的問題，有時需要使用特定資料結構儲存資料，接著使用該結構所對應的演算法解決問題。例如使用地圖搜尋最短時間內到達目的地的方式，地圖系統先要有大眾運輸系統的時間表，建立地圖上每一個地點到另一個地點的距離與移動時間，儲存在圖形資料結構內，地點轉換成節點，兩個節點(地點)之間可以連通，就新增一個邊，邊上的權重就是所需距離或移動時間，接著使用最短路徑演算法，找出距離最短或移動時間最少的路徑，就可以找輸出地圖上兩點之間的最短路徑或最短移動時間的規劃路線。

1-2 資料結構影響程式執行效率

如果要找尋n個數值的最大值，使用陣列(Array)儲存資料，需要一個一個比較才能知道最大值，此資料結構的找尋最大值程式所需時間為O(n)，O(n)的定義將於本章之後介紹，相當於與n(資料量)成正比。使用最大堆積(Max-Heap)找尋最大值所需時間為O(1)，表示為常數時間，將最大值刪除，調整為最大堆積，需要時間為O(log(n))，最大堆積(Max-Heap)會在之後章節介紹。如果不考慮建立最大堆積所需時間，最大堆積結構比陣列結構更適合找尋最大值，也就是相同的找最大值功能，使用陣列與最大堆積結構會獲得不同的執行效率，撰寫程式時，需要仔細比較不同的資料結構，找到合適的資料結構，能夠加速程式的執行效率。

1-3演算法的定義

為了讓電腦執行所需要的功能，先將所需要的功能轉換成演算法(Algorithm)，演算法是完成功能所需要的步驟，有了演算法才能轉換成程式。資料結構也需要提供操作資料結構的演算法，不然只有儲存資料的空間，沒有操作資料的功能，就不能算是完整的資料結構。

為了要讓電腦可以正確執行，演算法具有輸入(Input) 、輸出(Ouput) 、明確性(Definiteness)、正確性(Effectiveness)、有限性(Finiteness)之特性。

一、輸入

演算法可能有輸入，也可能沒有輸入，如果有輸入，需要明確的說明輸入的個數與每個輸入所表示的意義。

二、輸出

演算法至少一個以上的輸出，表示演算法執行後的結果。

三、明確性

所有演算法步驟都需要明確，演算法步驟不能有兩種以上的解釋，才能依照演算法轉換成程式碼。

四、正確性

演算法要能正確完成所需功能或解決問題，錯誤的演算法就需要修正。

五、有限性

電腦需要在有限步驟內執行程式，若演算法無法在有限步驟內完成，演算法就無法終止，轉換成的程式也無法執行完畢，無法獲得結果。

演算法的表示方式，可以使用文字、虛擬碼(Pseudo Code) 或流程圖(Flow Chart)進行表示，可以單純使用文字敘述解題步驟，也可以使用虛擬碼表示演算法，虛擬碼為類似程式碼的文字表示演算法，例如：利用「if」取代文字敘述的「如果」，還可以使用流程圖表示演算法，流程圖常用於幫助初學程式設計者，以圖示方式寫出解決問題的步驟，若能將解題流程以流程圖表示，就可以轉換成程式語言。

使用文字描述解題步驟，隨著問題的複雜度增加，可能無法清楚描述解題步驟。虛擬碼使用類似程式碼的文字描述解題步驟，但不能夠直接執行，雖然能快速轉換成程式碼，但適合已經有程式基礎的人員，初學者對程式沒有基礎，不適合使用虛擬碼。流程圖相較於文字敘述與虛擬碼，讓初學者更能掌握解題步驟，但需要先熟悉各種流程圖圖形所表示的意義，使用流程圖相較於文字與虛擬碼更適合初學者精確描述解題步驟。

我們要先瞭解流程圖的圖示，如下表。

假設要判斷一個數字是奇數還是偶數，使用文字敘述、虛擬碼與流程圖表示演算法，如下。以文字敘述表示演算法

若數字除以2的餘數等於0，則數字為偶數，否則數字為奇數。

以虛擬碼表示演算法

if num % 2 == 0:

print(num是偶數)

else:

print(num是奇數)

以流程圖表示演算法

1-4程式執行效率分析

程式執行效率要有共同的標準，通常以Big-O表示，Big-O是程式複雜度的上界，表示程式最差也會在此Big-O的複雜度以內，Big-O的定義如下。

O(h(n)) = { f | 存在正數C與正整數N，對於每個n>=N，使得0<= f(n) <= C*h(n) }

我們就可以說「h(n)是f(n)的上界」，f(n)一定不會超過h(n)。

程式複雜度越大表示越複雜，程式複雜度的大小關係如下，所需執行時間越長，如果執行複雜度為O(n)的程式需要花時間1秒鐘，則執行複雜度為O()的程式所需時間約為n秒鐘。

程式複雜度最小為O(1)，表示程式在常數時間內可以執行完畢，效率非常好。若程式的複雜度為O() 或O(n!)表示n值每遞增1，演算法執行時間需要花兩倍以上的時間。以下為O(log(n))、O(n)、O(n*log(n))、O()、O()、O()、O(n!)的成長趨勢圖，發現O()與O(n!)成長速度很快，複雜度為O()與O(n!)的程式，當n值不大時，程式還能夠執行完畢，當n值夠大時，可能就無法在有限時間內執行完畢

程式複雜度與能處理的資料量

一秒時間內可以執行的資料量，假設演算法效率為O(n)的程式，假設一秒鐘大約可以完成100000000個資料的運算，這個資料量的大小與電腦的中央處理器運算速度有關，隨著電腦每秒可以運算的指令數的增加，這個值會不斷成長。

由上表可知，若已知演算法複雜度為O(n!)，若題目規定計算時間只有3秒鐘，則輸入的資料量n就不能超過33，n超過33就有可能逾時，就需要想效率更好的演算法才行。

1-5 評估程式的複雜度

當寫好一個程式就需要評估程式碼的效率，會以輸入資料量來計算程式的複雜度，以下舉例各種複雜度的範例程式。

(1) O(1)

以下程式為比較兩數，回傳較大數值，程式的複雜度為O(1)。

if a > b:

return a

else:

return b

(2) O(log(n))

以下程式為二分搜尋演算法，已排序陣列中找尋某個值是否存在，則每次取一半，就可以逼近要找尋的數值，執行次數約為O(log(n))，所以程式的複雜度約為O(log(n))。

score = [45, 59, 62, 67, 70, 78, 83, 85, 88, 92]

mid=5

left=0

right=9

while score[mid] != 59:

print("檢查score[", mid, "]=", score[mid],"是否等於59")

if left >=right:

break

if score[mid] > 59:

right=mid-1

else:

left=mid+1;

mid=(left+right)//2

print("right更新為", right)

print("left更新為", left)

print("mid更新為", mid)

(3) O(n)

如果要找出n個數字的最大值，使用循序搜尋就需要將每個數字看過一次，所以程式複雜度與資料量成正比，就可以說搜尋程式的複雜度為O(n)。以下為循序搜尋程式，使用一層迴圈求解，該迴圈執行n次，所以程式的複雜度為O(n)

a = [6, 7, 4, 5, 2, 8, 3]

n = 7

max = 0

for i in range(n):

if max < a[i]:

max = a[i]

print(max)

(4)O(n*log(n))

以下為合併排序，mergesort函式每次將資料拆成一半，合併排序的mergesort的遞迴深度為O(log(n))，而merge函式每一層都需要O(n)，所以合併演算法效率為O(n*log(n))，排序單元會詳細介紹合併排序演算法。

a=[60,50,44,82,55,24,99,33]

tmp=[0,0,0,0,0,0,0,0]

def merge(L, M, R):

left=L

right=M+1

i=L

while (left <= M) and (right <= R):

if a[left]<a[right]:

tmp[i]=a[left]

left = left + 1

else:

tmp[i]=a[right]

right = right + 1

i = i + 1

while left<=M:

tmp[i]=a[left];

i = i + 1

left = left + 1

while right<=R:

tmp[i]=a[right]

i = i + 1

right = right + 1

for i in range(L, R+1):

a[i]=tmp[i]

def mergesort(L,R):

if L < R:

M=(L+R)//2

mergesort(L,M)

mergesort(M+1,R)

merge(L,M,R)

print("L=", L, "M=", M," R=",R)

for item in a:

print(item,' ', end='')

print()

(5) O(n^2)

以下程式為九九乘法表，兩層迴圈各執行n次，所以程式的複雜度為O(n^2)。

n = 10

for i in range(1, n):

for j in range(1, n):

print(i, '*', j, '=', i*j, '\t', sep='',end='')

print()

(6) O(n^3)

以下程式為Floyd Warshall找尋最短路徑演算法的部分程式碼，三層迴圈各執行n次，所以程式的複雜度為O(n^3)。

n = len(City)

for k in range(n)):

for i in range(n):

for j in range(n):

if dis[i][k]==1000000 or dis[k][j]==1000000:

continue

dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])

(7)O(2^n)

以下為費式數列的遞迴程式，因為F(k)需要遞迴求解F(k - 1)與F(k - 2)，若k值很大時，k值下降速度很慢，相當於一分為二，程式效率為O(2^n)。

def F(n):

if n == 0 or n == 1:

return 1

else:

return F(n - 1) + F(n - 2)

n = int(input("請輸入n值？"))

result = F(n)

print("F(", n, ")=", result)

(8)O(n!)

以下程式列出n個數值的各種排列，有n!種排列方式，所以程式顯示至少n!次，此程式效率至少O(n!)，甚至O(n^n)。

def perm(curStep):

if curStep == n:

for i in range(n):

print(num[step[i]], " ", end="")

print()

else:

for i in range(n):

success = True

for j in range(curStep):

if step[j] == i:

success = False

break

if success:

step[curStep] = i

perm(curStep+1)

perm(0)

在撰寫程式時，若遇到程式效率為O(2^n)或O(n!)，當n值不大還可以接受，當n值較大時，就需要考慮以更有效率的演算法撰寫程式。

Page updated

Google Sites

Report abuse