第 14 章 資料結構與演算法.

Presentation on theme: "第 14 章 資料結構與演算法."— Presentation transcript:

1 第 14 章 資料結構與演算法

2 學習目標 看完本章, 您應該學會以下主題： 什麼是資料結構 主要的資料結構類型與應用 資料結構與演算法對程式的影響

3 14-1 何謂資料結構 在第 5 章提到電腦存放資料的方式主要有文字、整數、浮點數等格式, 而大部份的高階語言也都提供對應的基本資料型別 (Data Type), 以便我們在程式中定義合適的變數來存放資料。

4 14-1 何謂資料結構

5 14-1 何謂資料結構 當程式要處理的資料很多時, 我們則需要一種特別的資料組織方式, 以便程式能以較有效率的方式存取、處理這些資料, 提昇程式的效率, 而這個組織資料的方式就稱為資料結構 (Data Structure)。 當我們指『資料結構』這門學問時, 則要用英文複數形式 Data Structures 來稱呼之。

6 14-1 何謂資料結構 舉例來說, 我們要以程式處理全班 40 位同學的國、英、數各科成績時, 想當然爾會將每位同學的學號和成績放在一起以方便處理, 而不會東一個、西一塊, 因此您可能會這樣存放：

7 14-1 何謂資料結構 不過可能有人會改用下面這種方式：

8 14-1 何謂資料結構 要使用何種方式, 除了與程式的用途、寫法有關, 有時也需考慮記憶體容量、程式語言的支援度。但首先我們都必須認識有哪些資料結構可使用, 以下就來介紹一些基本的資料結構及應用。

9 14-2 陣列 陣列 (Array) 算是最基本也最簡單的資料結構, 它是將多筆資料連續地放在記憶體中, 程式可透過索引來取得存於陣列中的任一筆資料。在處理大量『同類型』的資料時, 經常會使用陣列, 因此幾乎所有的高階語言都內建支援建立陣列結構的語法。 陣列可依其維度 (Dimension) 分為一維陣列、二維陣列、或三維以上的多維陣列, 以下先介紹最簡單的一維陣列。

10 一維陣列 前面所舉的成績資料存放方式, 就可視為陣列的應用, 例如存放所有學生英文分數的陣列。

11 一維陣列 像這樣可存放 40 個元素的陣列, 我們就會稱此陣列的大小為 40, 或是長度為 40。陣列只能用來存放同一類型的資料型別, 因此在程式語言中宣告 (Declare) 一個陣列時,都要事先指定此陣列是用來存放什麼資料型別的資料。

12 一維陣列

13 一維陣列 要存取陣列中各元素的值時, 就必須透過『索引』值來指定要使用的是第幾個元素。要注意的是, 許多高階語言的陣列索引值都是由 0 開始, 而非由 1 開始, 因此像前面例子中『1 號同學』的分數, 會是存在第 0 個元素中, 而非第1 個元素：

14 一維陣列

15 一維陣列 但也有部份語言是由 1 開始替陣列元素編號, 甚至早期的 Visual Basic 語言還允許程式設計者自行指定元素的起始編號, 例如 "Dim a(-2,3)" 所建立的是含 6 個元素的陣列, 其元素索引分別是 -2、-1、0、1、2、3。

16 一維陣列 不論是存於前面、中間、後面的元素, 我們只要指定元素的索引值, 即可取得該元素中所存放的資料, 因此陣列的優點就是可以快速、方便的存取資料結構中的資料。 而陣列也有一項明顯的缺點：在大多數的程式語言中, 陣列的大小是不能變動的, 亦即一旦宣告陣列變數後, 這個陣列的大小就固定了, 不能再增加或減少元素：

17 一維陣列

18 二維陣列 如果把一個 CD 架看成是一個陣列, 這時每一個可置入 CD 收納盒的格子就相當於一個陣列元素。單單一排的 CD 架就可視為是『一維陣列』 (One-dimensional Array), 如果把好幾排的 CD 架組合起來, 就是一個有縱向與橫向的『二維陣列』 (Twodimensional Array)。或者說, 二維陣列是由 2 個或 2 個以上的一維陣列所組合而成的陣列。

19 二維陣列

20 二維陣列 以 C/C++ 語言為例, 要宣告二維陣列, 就是在宣告時指定兩個維度即可：

21 二維陣列

22 二維陣列 二維陣列的應用相當多, 例如在做數學的矩陣運算時, 我們即可將矩陣的內容看成是一個二維陣列, 讓矩陣中每個元素分別儲存到對應位置的陣列元素中。

23 二維陣列 此外在表示多項式時, 也常會用有兩列的二維陣列, 一列用來記錄羃次, 一列則用來記錄各項的係數, 例如：

24 二維陣列 生活化的應用也可使用陣列, 例如我們可用二維陣列來表示課程表：

25 二維陣列

26 二維陣列 圖中將課表改成橫列也是一項技巧, 若依傳統的直式課表表示法, 並依樣將其內容一一對應放到一個 schedule[4][5] 的陣列中, 此時要存取陣列元素時, 變成要先指定第幾節、再指定星期幾, 較不自然, 讀者可自行練習畫出這樣的陣列內容, 即可瞭解。

27 隨堂練習 1.若要用二維陣列表示多項式 6X3 + 5X2 - 3X + 8 的內容, 請畫出各陣列元素所記錄的內容。

28 14-3 鏈結串列 鏈結串列 (Linked List) 也是一個相當基本的儲存資料之方式, 其特點就如名稱所示, 是將儲存的資料像鏈子一樣將它們串在一起。 『串起來』的意思是說每筆資料都會再記錄它的下一筆資料在記憶體中的位址, 因此即使前後資料存放在記憶體中是不相鄰而散亂在各處, 程式仍可透過所記錄的位址輕易找到下一筆資料, 因此感覺資料仍是串在一起而非分散的。

29 14-3 鏈結串列

30 14-3 鏈結串列 鏈結串列除了記錄下一筆資料的位址外, 也可再多記錄前一筆資料的位址, 如此一來程式就能向前或向後找下一筆資料, 這種結構就稱為『雙向』鏈結串列；而只能往一個方向找下一筆的則稱為『單向』鏈結串列, 以下就先介紹單向鏈結串列的原理與應用。

31 單向鏈結串列 單向鏈結串列 (Single Linked List)中的每個元素稱為節點 (Node), 每個節點都會記錄下一個節點所在的記憶體位置, 換言之, 以記錄同樣數量的資料來考量, 單向鏈結串列所需的記憶體空間會比使用陣列時, 用掉更多的記憶體。 由於這種『指向下一個節點』的特性, 所以單向鏈結串列很適合用來表示一組有次序性的資料。此外, 通常也會額外用一個未記錄資料的節點來代表開頭 (Head)。

32 單向鏈結串列

33 單向鏈結串列 相較於陣列結構, 鏈結串列是個『以空間換取時間』的例子, 因為它使用額外的記憶體空間來記錄下一個節點的位址, 因此只要改變『下一個節點』這個欄位所記錄的資料, 就能改變整個串列的內容：例如改變節點的順序、插入新節點、刪除既有節點等。

34 單向鏈結串列

35 單向鏈結串列

36 單向鏈結串列 如果要插入的不只是一個節點, 而是另外一個串列, 其操作方式也類似, 只要將插入位置的前一個節點指向新加入串列的開頭、新加入串列的結尾指向插入位置的後一個節點, 即可大功告成。

37 單向鏈結串列 反之在陣列結構中要做改變元素的順序、插入新資料、刪除既有資料等操作, 都必須做許多搬移資料的動作, 也就是說要花較多的時間才能完成類似的操作。 另一方面, 鏈結串列的缺點則是要存取位於串列中、後段的節點較不方便, 都要從串列開始往後一個個讀取；反之在陣列中只要指定索引, 就能立即取得索引位置上的元素值。

38 環狀串列 如果我們讓鏈結串列中的最後 1 個節點指向第 1 個節點, 就成為一個環狀串列, 可用來表示有循環性的資料。

39 雙向鏈結串列 若鏈結串列中的每個節點除了記錄下個節點所在的記憶體位置, 也再記錄『前一個』節點所在的位置, 就成為雙向鏈結串列 (Double Linked List), 此時不但可由前往後讀取串列, 也可由後往前讀, 而為了方便由後往前讀, 通常會再用一個代表結尾的 Rear 節點指向串列的結尾。

40 雙向鏈結串列

41 雙向鏈結串列 在資料量相同的情況下, 雙向鏈結串列又比單向鏈結串列多用掉許多記憶體空間, 但相對的則提供了可向前或向後搜尋節點的便利性。雙向鏈結串列當然也能任意改變節點的次序、新增/移除節點, 只不過要比使用單向鏈結串列時多處理『前一節點』的相關資訊。

42 雙向鏈結串列

43 雙向鏈結串列

44 雙向鏈結串列 雖然在雙向鏈結串列進行新增/移除節點等操作時要比單向鏈結串列多一些動作, 不過由於可由後往前讀取各節點, 也使雙向鏈結串列多了一些使用上的方便性。

45 隨堂練習 1.若改用下圖節點結構來建立表現多項式的單向鏈結串列, 請畫出多項式 6X3 + 5X2 -3X+ 8 所構成的串列內容。

46 14-4 堆疊與佇列 堆疊 (Stack) 與佇列 (Queue) 兩種資料結構, 在日常生活中即可看到許多實際的例子, 而許多應用程式在處理資料時, 也常會用到這兩種資料結構。

47 堆疊 堆疊的特性 堆疊 (Stack) 是指一種後進先出 (LIFO, Last In First Out) 的資料結構, 也就是說, 放入此結構 (集合) 中的物件 (資料) 要被取出時, 最先被取出的會是最後一次放進去的資料；而要取得其它早先放進堆疊的資料, 必須等比它後加入的物件全部被拿出來後, 才能將它拿出來。例如我們生活中看到的一疊盤子, 就可視為是一種堆疊結構：

48 堆疊的特性

49 堆疊的特性 由盤子的堆疊可以發現堆疊的幾個主要特性：
堆疊中的資料是有次序性的, 例如我們依序放入紅、白、藍的盤子, 由上而下的順序就是藍→白→紅。如果要改變次序, 就必須將盤子拿出來再重新放入, 不可像表演特技般隨便從中間抽出盤子來改變其次序。 對於堆疊中資料的處置動作都只發生在堆疊結構的頂端, 例如一疊盤子的最上端, 要放入/取出盤子都只能從最上面做, 不可從中間、下面做放入/取出的動作。

50 堆疊的特性 在程式中實作堆疊結構時, 通常是用陣列來實作之。例如宣告含 10 個元素的陣列當成堆疊使用, 就表示這個堆疊最多可放 10 個物件。程式除了要提供放入物件 (稱為 push) 及取出物件 (稱為 pop) 功能外, 也要用變數記錄目前堆疊的『頂端』 (可放入新物件的位置) 是位於第幾個元素, 這樣在 push 另一筆資料進來, 或 pop 一筆資料出去時才不會處理錯誤。

51 堆疊的特性

52 堆疊的特性

53 堆疊的特性 用陣列來實作堆疊的好處就是結構簡潔易用, 缺點則是陣列的空間是固定的, 因此堆疊的大小也是固定的。
如果想讓堆疊有可大可小的彈性, 則可用單向鏈結串列來實作堆疊：當程式要 push 一筆資料到堆疊時, 即配置新節點的儲存空間, 並將該節點接在鏈結串列的開頭；要 pop 資料時, 則將串列中的第 1 個節點的資料取出, 並將該節點自鏈結串列中移除。

54 堆疊的特性

55 堆疊的特性

56 堆疊的特性

57 堆疊的應用 不但在生活中隨處可見堆疊的實例, 在電腦應用中也可常見堆疊的應用。例如要做電子鼠走迷宮的比賽, 就可用堆疊記錄先前走過的叉路, 走到沒路時才可退回去選其它的路。更基本的應用, 則是在電腦系統中處理函式呼叫 (Function Call) 時, 以堆疊記錄程式的位址及傳遞參數。

58 堆疊的應用 前一章提過作業系統或一些應用程式通常會以函式的形式, 提供一些基本功能供我們所撰寫的程式呼叫。當我們的程式呼叫函式時, 表示程式的執行流程要暫時轉移到函式之中, 待函式執行完畢才返回我們程式未完的部份繼續執行；此外當呼叫函式時, 通常也需傳遞『參數』給函式, 例如呼叫『開啟檔案』的函式, 就需傳遞『檔案的路徑、名稱』為參數。為達成上述的目的, 許多系統都採用堆疊來記錄相關的資訊：

59 堆疊的應用

60 堆疊的應用

61 佇列 佇列的特性 佇列 (Queue)和堆疊一樣, 都限制只能從單一方向放入及取出資料, 但兩者有一項很大的差異：堆疊 push 及 pop 都發生在同一端；但佇列則是放入及取出資料是在不同端, 因此形成一種先進先出 (FIFO, First-In-First-Out) 的資料結構, 同樣在生活中可以發現很多佇列的例子, 例如小朋友玩溜滑梯、火車過山洞時, 滑梯和山洞就是個佇列；只要沒人插隊或中途離開, 排隊買票、結帳也是一種佇列的例子。

62 佇列的特性 將資料放入佇列的動作稱為 “enqueue”, 從堆疊取出資料則稱為 “dequeue”。

63 佇列的特性 佇列同樣可用陣列或鏈結串列來實作之。以陣列實作時, 必須用兩個變數來記錄佇列的開頭 (Fore) 及結尾 (Rear)。一般習慣將開頭指向佇列中第 1 筆資料的前一個元素, 而結尾則指向最後一筆資料的位置：

64 佇列的特性

65 佇列的特性 如圖 所示, 在佇列加入一筆資料時 r 會向後移一位；而 f 也會在取出資料時向後移一位。如此會發生一個問題：當 r 已經到了陣列最後 1 個元素時, 佇列就再也不能容納資料, 這個佇列也變得沒用了。 解決方法之一, 就是每當從佇列中取出一筆資料而空出前面的空間時, 就將整個陣列的內容都向前移一位 (就像我們排隊買票時, 有人買好離開, 我們就向前移動), 讓佇列能一直空出後面的位置、重複使用。

66 佇列的特性 但這樣做有個缺點：將陣列中的元素逐一向前移動是個費時的操作, 對程式的執行效率會有負面的影響。
另一個方案則是讓 f、r 在到達陣列結尾時, 可以再跳到陣列的開頭, 讓前面空出來的元素, 又能用來存放新加入佇列的資料。這就好像把陣列前後連接起來, 形成一個環狀的佇列：

67 佇列的特性

68 佇列的特性 如圖 的方式, 就能讓空間有限的佇列, 也能一直重複使用, 發揮最大的效益。但要注意的是, 使用環狀佇列時, 就不能讓資料放滿整個陣列, 當陣列只剩一個元素未被佔用時, 就要視為『佇列已滿』。

69 佇列的特性 像圖 (c)就是『佇列已滿』的例子, 因為在此圖中若再放一個 G 到佇列中, 此時 r 和 f 都會變成 1, 但在圖 已說明過, r 和 f 相等時代表『佇列是空的』！因此為了不讓程式誤判, 所以只好讓代表佇列的陣列永遠都要空出至少一個元素的空間。

70 佇列的應用 佇列的應用也相當廣, 以電腦為例, 在多工作業系統中處理工作的排程 (Job Scheduling) 時, 若採用 FCFS 排程演算法 (參見 節), 就是將來自每個處理程序的要求排入佇列中, 讓它們可輪流使用 CPU 達到多工的目的。 另外像作業系統也是用佇列來處理多個列印要求, 待一份文件的列印工作全部送到印表機輸出後, 再繼續處理佇列中下一份列印工作。

71 佇列的應用 而個人電腦的鍵盤處理機制也是使用佇列, 當我們按下的按鍵資訊經由 BIOS 處理後送到電腦中, 就是存於記憶體中一小塊被用來當鍵盤緩衝區的佇列中, 等待作業系統來處理。 相信許多人都有如下的經驗, 如果系統正在忙碌, 我們又拼命按了一堆按鍵, 此時電腦會開始嗶嗶叫, 這就是因為持續按鍵造成佇列已滿, 而電腦就透過嗶嗶聲來請我們手下留情別再按了。

72 佇列的應用

73 隨堂練習 1.若堆疊中已有內容為 {1,2,3} (左邊為底端, 右邊為頂端), 接下來依序做 pop、push(4)、pop、pop、push(5) 的動作後, 堆疊的內容為何？ 2.如果用單向鏈結串列來實作佇列, 請說明『加入一個元素到佇列』、『由佇列取出一個元素』的操作過程。

74 14-5 樹狀結構 樹狀結構的基本觀念 樹狀結構 (Tree, 或簡稱樹) 也是相當重要的資料結構, 例如家譜就是一種樹狀結構, 在家譜中, 每個人物的上下、左右關係都能表現得井然有序, 因此樹狀結構很適合用來表現具有次序性、階層性、從屬性的資料。 例如在電腦中, 有許多檔案系統都是用樹狀結構在管理的, 而目前常見的資料庫管理系統, 其內部更是會利用樹狀結構來做資料的排列與管理。

75 樹狀結構的基本觀念

76 樹狀結構的基本觀念 樹是由多個節點 (Node) 所組成的結構, 其中有一個最特別的節點稱為根 (Root) 節點, 至於其它的節點則分散於一或多個分枝子集合中, 每個子集合也可視為一個樹, 也就是整個樹的子樹 (Subtree)。 每個節點相對其上層的節點稱為子 (Child) 節點, 相對於其下層時則稱為父 (Parent) 節點, 而同一層的節點則可稱為兄弟；沒有子節點的末端節點稱為 Leaf (樹葉)。至於樹的高度也可稱為深度 (Depth) 或階度 (Level)。

77 樹狀結構的基本觀念

78 以鏈結串列實作樹狀結構 樹可用鏈結串列來表示, 有一種表示方式是讓每個子樹自成一個串列, 而每個節點又和它的子樹串列的開頭及樹葉節點也形成一個串列, 所以看起來是個串列與串列交叉成形的結構, 如圖 所示。

79 以鏈結串列實作樹狀結構

80 以鏈結串列實作樹狀結構 不過像上述這種用法實在有點複雜, 這是因為未對子節點、子樹的數量加以限制所致。為了方便使用, 通常會使用只限有兩個子樹或子節點的二元樹。

81 二元樹 所謂二元樹 (Binary Tree) 是指每個節點的子樹或子節點最多只能有兩個, 由於子樹最多只有兩株, 所以我們可明確稱它們為左子樹及右子樹, 或稱其兩個子節點為左子節點 (Left Child) 及右子節點 (Right Child)。此時可將節點的結構略做調整, 讓節點能同時指向左子樹和右子樹, 整個資料結構也會簡化許多。

82 二元樹

83 二元樹 如圖 的表現方式, 即可輕易由任一節點找到其左右子節點, 不像非二元樹要找子節點可能要先經過其它節點的不便。

84 以陣列實作二元樹 如果二元樹中除了最下一層的樹葉節點外, 每一層的節點都有左右兩個子節點, 此時這個二元樹就稱為完滿二元樹 (Full Binary Tree), 我們可以很容易算出, 完滿二元樹的節點總數為 2n-1 (n 為樹的層數), 例如 5 層的完滿二元樹共有 25-1=32-1=31 個節點。 如果每個節點都依序予以編號, 我們就能用陣列的方式來表示二元樹。而且此法也能用來表示非完滿二元樹, 只要將無節點位置所對應的陣列元素留空即可, 如下圖所示：

85 以陣列實作二元樹

86 以陣列實作二元樹

87 以陣列實作二元樹 要存取第 n 個節點的父節點、子節點時, 可依如下的規則計算：
父節點在 n/2 的位置, 若 n 為 1 則為根節點, 所以沒有父節點。 左子節點在 2n 的位置, 若 2n 超出陣列範圍, 表示它沒有左子節點。 右子節點在 2n+1 的位置, 若 2n+1 超出陣列範圍, 表示它沒有右子節點。

88 以陣列實作二元樹 這種表現方式的缺點是若二元樹的內容非常『不完滿』, 則會浪費較多的儲存空間, 如圖 陣列中第 5、8、9、10、11 個元素的空間都未用到, 此外尋找節點時還要另外做計算。因此有另外一種以二維陣列記錄二元樹的方式, 陣列的大小為：節點個數× 3, 如圖 所示。

89 以陣列實作二元樹

90 二元樹的應用 二元樹的應用相當廣泛, 許多需要將資料排序, 以便能用儘快找到資料的應用, 都會使用二元樹來排列資料, 也就是所謂的二元搜尋樹 (Binary Search Tree)。 其特點是每個節點的值都大於左子樹的值, 而小於右子樹的值。圖 即為連續輸入 5 筆數字資料建立二元搜尋樹的例子。

91 二元樹的應用

92 二元樹的應用 建好二元搜尋樹後, 每次要搜尋某一筆資料時, 就從根節點開始, 一直往下做比較大小的動作： 比節點值小就走左邊。
比節點值大就走右邊。 到樹葉節點都沒找到, 表示樹中沒這筆資料。

93 二元樹的應用 像資料庫管理系統為了能快速找到所需資料所用的索引 (Index) 結構, 也是應用類似的觀念, 但因資料庫資料量龐大, 若用二元搜尋樹來建立索引, 將會形成一個非常深的樹狀結構, 如此一來搜尋效率也不佳。 因此一般資料庫都是使用稱為 B-Tree 或 B+-Tree 的樹狀結構：其特點是每個節點會含有多筆資料、非樹葉節點也都有兩個以上的子節點, 以提供較佳的搜尋效率。

94 二元樹的應用 另外像電腦下棋程式, 也會用決策樹 (Decision Tree) 或遊戲樹 (Game Tree) 來決定要如何進行遊戲, 並從中選擇出較佳的決策或棋步。若電腦運算能力愈強, 就能推算更多可能的狀況與棋步, 並進一步選出較佳的棋步來擊敗對手。

95 隨堂練習 1.請問 6 層的完滿二元樹共有幾個節點？
2.請試將星期一到星期天的英文單字放在二元搜尋樹中, 若要讓搜尋任一個單字最多只要三個節點即可找到, 應如何擺放？

96 14-6 演算法簡介 何謂演算法 前一章曾說過：解決問題的方法就是演算法, 但這是個廣義的說法。若要更嚴謹地地描述電腦程式所用的演算法, 則我們可說演算法是可完成特定工作的一組指令集合, 且滿足以下的 5 個條件：

97 14-6-1 何謂演算法 演算法可由外部取得輸入資料。 演算法至少會產生一個輸出結果。 演算法中各個指令的意義都必須是明確不模糊的。
演算法的指令是有限的, 在所有可能情況下, 演算法都會在有限的步驟內完成其工作。 演算法的每個指令都必須夠簡明、有效率, 即使不用電腦, 僅用紙、筆也能完成所有動作。

98 何謂演算法 在表示演算法時, 通常會使用前一章提過的虛擬碼或流程圖, 虛擬碼就是用簡單的文字敘述 (通常會使用接近程式語言的語法) 來說明演算法的每個步驟。 舉例來說, 我們要用程式尋找從 1 到 n (任何比 1 大的自然數) 之間所有的質數, 最簡單的演算法可能是將每一個要檢查的數值, 逐一除以比它二分之一還小的數值, 如果都不能整除, 表示它是質數 (例如 11 不能被 2、3、4、5 整除)。此演算法可寫成如下的步驟：

99 何謂演算法

100 14-6-1 何謂演算法 對同樣的問題, 使用不同的演算法時對程式的執行效能可能會有很大的影響。
例如上述計算質數的例子, 如果我們將計算除法時的除數, 是由 2 算到 n-1, 如此雖然也能算出範圍內的所有質數, 但顯然多浪費許多時間做不必要的計算。例如判斷 13 是否為質數時, 用上面所列的方法, 計算到除數為 6 仍不能整除時, 即可得知 13 為質數；但用計算到 n-1 的方法則要多算到除數為 12 才能判斷 13 為質數, 顯然白白多算了許多次。

101 何謂演算法 當然, 上列的求質數方法仍非最佳的演算法, 因為它仍做了許多不必要的計算, 例如所有用非質數當除數的計算, 都是不必要的, 例如 13 不能被 2 整除, 後面除以 4、除以 6 的計算也是多餘的。 所以我們又可找出一個更快的方法：

102 何謂演算法 建立一個陣列, 存放已算出的所有質數 (一開始只有 2), 而在做除法運算時, 只用此陣列中的質數當除數：都不能整除時即將被除數加到陣列中；會被陣列中任一數整除者, 則為非質數。利用這個方法我們又可使計算的過程減少許多。

103 何謂演算法 然而在選擇演算法時, 也不盡然都選擇最快的方法, 因為有時最快的方法可能會多用掉一些記憶體空間 (例如上述計算質數的簡例, 較快的方法要多用一個陣列來存放質數)。 對某些小型的電腦系統 (例如嵌入式系統), 其可用的記憶體可能不是很充裕, 可能根本就不敷我們的程式使用, 此時我們就需折衷選擇效率稍差一點, 但使用記憶體較少的演算法, 讓程式可以執行。以下簡介一些演算法的應用範例, 讓讀者對演算法有更具體的認識。

104 演算法的實例應用 氣泡排序法 可處理大量資料的優越能力是電腦之所以應用如此廣泛的主因之一, 而在處理大量資料的場合, 常見的基本處理就是要先將資料排序 (Sorting), 因為一旦資料依順序排好後, 之後要查詢、讀取、處理等都方便許多。

105 氣泡排序法 在各種排序法中, 最普通的一種演算法稱為氣泡排序法 (Bubble Sort)。因為在排序過程中, 資料在其存放的結構中的位置, 是一個個地向前或向後移動, 就好像一個氣泡由水底浮到水面的過程一樣, 所以稱為氣泡排序法。

106 氣泡排序法 氣泡排序法的道理很簡單, 以排序陣列中的元素為例, 過程如下：
從最後面的元素開始, 將每個元素與前一個元素所存放的值相比較, 如果前者小於後者, 就將兩個值的位置對調, 如此一直比較到陣列開頭, 此時整個陣列中最小的元素值就已移到陣列開頭了。

107 氣泡排序法 第 2 輪則排除陣列開頭的最小值, 再將後面所有元素依同樣方式做比較、對調位置, 讓次小值移到最小值之後。
第 3 輪排除前兩個元素, 再將後面所有元素依同樣方式做比較、對調位置...。如此一直做下去, 直到最後一輪只需比較最後兩個元素, 若最後的元素值較小, 即將它移到前面, 如此即完成排序。

108 氣泡排序法

109 氣泡排序法

110 氣泡排序法 氣泡排序法的演算法相當直覺, 就是逐一比較相鄰的 2 個元素, 讓最小值逐次向前移動以完成排序。但由圖 也可發現, 其效率並不是很好, 因為有些比較都重複做許多次, 此外對調的動作是比較耗時的一項動作, 如果不巧較小值大多集中在陣列後方, 或陣列較大時, 則氣泡排序法逐一比較、對調將會花費較多時間。

111 氣泡排序法 如果想改成由大到小的排列, 原理相同, 只是在比較元素時, 改成將較大的元素值往前移, 較小的元素值往後移。

112 分而治之的演算法應用 在各種演算法的應用中, 有一種常見的設計方法稱為分而治之 ( Divideand Conquer), 顧名思義, 這種設計方法是將某個問題分成多個相似、同類型的子題, 而子題又進一步分成更再小的子題, 如此一直細分下去, 分到最後要解決的就是個簡單的小問題, 將小問題解決了再集合起來, 就完成整個工作。

113 分而治之的演算法應用 舉例來說, 計算階乘就是個最典型的可用分而治之的方式解決的問題。N! 就是 N × (N-1)× (N-2) × ...× 3 × 2 × 1 的乘積, 假設要寫個計算階乘的程式, 我們當然不可能把程式寫成從 1 乘到 N, 如果要乘到 20, 就要在程式中寫上20 個數字相乘, 不但沒效率, 而且如果接下來要算 30!, 又要修改程式多寫 10 個數字。此時就可應用分而治之的方式來解決：

114 分而治之的演算法應用 N! 可看成是 N × (N-1)!, 所以要先算出 (N-1)!
.... 最後要算的就是 2 × 1!, 程式只要定義 1!=1, 即可算出 2 × 1!=2..., 如此一直倒推回去即可求得 N! 的值。

115 分而治之的演算法應用

116 分而治之的演算法應用

117 分而治之的演算法應用 圖 (b) 的程式用到一項分而治之演算法常見的實作技巧, 稱為遞迴 (Recursion), 所謂遞迴函式 (Recursive Function) 就是讓函式自己呼叫自己, 藉此達到簡化程式。

118 分而治之的演算法應用 在排序法中也有一種應用分而治之的排序演算法, 稱為快速排序法 (Quick Sort)。
簡單的說, 其排序方式是先選定一個值, 然後將待排序的內容分成『小於等於該數值』及『大於該數值』兩部份, 並讓它們分別放在選定值的左、右兩邊 (或者說把選定值安插到這兩部份的中間), 如此一來就表示選定的值已經擺到排序後的正確位置了。

119 分而治之的演算法應用 而分開的兩部份, 又可各自依相同的方式分解..., 如此一直細分下去, 每次都至少會有一個數值移到『正確位置』, 細分到最後不能再分時也表示該小部份都排好, 各小部份都排好, 也表示全部的資料都完成排序。

120 分而治之的演算法應用

121 分而治之的演算法應用

122 分而治之的演算法應用 就較費時的資料對調動作而言, 快速排序法通常可比氣泡排序法少很多, 雖然實際的排序速度仍要依資料分佈的情況而定, 但可以確定的是快速排序法不會比氣泡排序法還慢。

123 演算法的執行效率 在評估一個演算法好不好時, 通常會用演算法的時間複雜度 (Time Complexity), 雖然名稱中有時間, 但並不表示執行時的絕對快慢, 因為同樣的程式在配備不同 CPU 的電腦上, 執行的速度也顯然會不同。因此評估的重點是演算法中各動作的執行次數, 通常以 Big O 表示法(Notation) 來表示演算法的快慢。

124 演算法的執行效率 Big O 表示法是以 O(f(N)) 來表示處理 N 筆資料所需的時間複雜度, 例如有個演算法的時間複雜度為 O(N) 時, 表示此演算法耗費的步驟 (時間) 和資料量成正比；若另一個相同功能的演算法, 其時間複雜度為 O(N2), 則表示其耗費的步驟 (時間) 和資料量平方成正比, 換言之只要資料量大幅增加, 其處理速度就會變得非常的慢。

125 演算法的執行效率

126 演算法的執行效率 以本章提到的兩個排序法為例, 氣泡排序法的平均表現為 O(N2), 而快速排序法的平均表現則為 O(N log N), 因此平均而言, 快速排序法的效率是優於氣泡排序法。

127 隨堂練習 1.請寫下 {43,68,10,35,27} 這個數字陣列用氣泡排序法排序時, 每一輪的結果。
2.請回顧第 13-3 節中提到的幾個計算最大公因數的程式, 並判斷何者是使用遞迴呼叫方式。

128 特別企劃－電腦如何下棋、玩遊戲？ 在1988年時, 當時世界西洋棋棋王 Gary Kasparov 還公開表示：電腦在 2000 年前是無法打敗大師級的西洋棋棋士。但結果棋王提出這個說法還不到十年, IBM 的深藍 (Deep Blue) 電腦就在一場 6 局的棋賽中, 以兩勝三和一負的成績打敗 Gary Kasparov。

129 特別企劃－電腦如何下棋、玩遊戲？ 雖然電腦在連續長時間的棋局中不會像人一樣產生疲倦、沮喪等負面情緒也是致勝因素之一, 但無論如何, 這場讓棋王吃鱉的比賽仍是人工智慧中遊戲理論(Game Theory) 應用的一大成就。

130 特別企劃－電腦如何下棋、玩遊戲？ 電腦之所以會下棋, 甚至還能下贏棋王, 其原理並不難, 基本上電腦是將每局棋各種可能的走法都建立成一個遊戲樹 (Game Tree) 的結構：

131 特別企劃－電腦如何下棋、玩遊戲？

132 特別企劃－電腦如何下棋、玩遊戲？ 建好遊戲樹後, 下棋程式會用最小 - 最大值 (Min-Max, 取 Minimum、Maximum 的字首,也可寫成 Minimax) 演算法來決定要走哪一步。其方式是用一狀態函數來決定樹葉節點的『分數』, 以西洋棋為例, 決定分數的要素包括國王受保護的程度、棋子的數量、棋子的位置等。

133 特別企劃－電腦如何下棋、玩遊戲？ 若是玩象棋, 車傌炮的數量、位置的重要性可能大於兵卒, 所以車傌炮都沒死可得較多分數...；當然對手的狀態、棋子的種類也都要予以考慮, 例如自己的兩炮都存活時可加 5 分, 則對方的雙包也都存活時則減 5 分...。

134 特別企劃－電腦如何下棋、玩遊戲？

135 特別企劃－電腦如何下棋、玩遊戲？ 經過一番計算後, 即可得到各樹葉節點的『分數』, 接著就要用最大-最小值的方式來決定最佳走法, 所謂最大值即表示當輪到電腦下時, 電腦當然是會選擇分數最高的走法；但對手走的時候則當然是選分數最低 (電腦評分低的盤面, 就是對手有利的盤面) 的走法。 換言之, 輪電腦走時, 該節點的分數是取子節點分數的最大值 (Max)；而對手走時, 該節點的分數則是取子節點分數的最小值 (Min)。

136 特別企劃－電腦如何下棋、玩遊戲？

137 特別企劃－電腦如何下棋、玩遊戲？ 依此運作原理, 電腦能『思考』的遊戲樹愈深、愈廣, 其下法將愈無懈可擊。然而西洋棋的盤面變化何止千億種, 既使是像深藍這樣快速的電腦, 也很難在『有限時間內』完成足夠算出最佳走法的計算, 因此對這種變化萬千的棋局, 需套用 α-β 縮減法 (Alpha-Beta Cut-off) 來減少計算的數量。

138 特別企劃－電腦如何下棋、玩遊戲？ α-β 縮減法的道理也很簡單, 在評估各樹葉的分數時, 我們先由左至右依次計算, 對需取 Max 值的那一層節點, 由於其上的 MIN 節點只會取最小值, 所以這個最小值即為再上一層 MAX 節點的 α 值。 之後在評估其它孫子 MAX 層的分數時, 只要已算出一節點分數小於 α 值, 同一子樹下的其它 MAX 節點就不必再考慮了, 可跳過改算另一 MIN 子樹下的 MAX 節點, 如此將可節省不少計算時間。

139 特別企劃－電腦如何下棋、玩遊戲？

140 特別企劃－電腦如何下棋、玩遊戲？

141 特別企劃－電腦如何下棋、玩遊戲？ 至於 β 值的原理也相似, 只不過 β 值是用在 Min 層, 也就是說它是由其下的 Max 層取得的一個下限值。若上圖的例子再延伸到第 4 層時, 則只要第 3 層的 Max 節點出現大於β 值的結果, 其下的其餘子樹就不必再算了。 透過這種方式, 雖然可讓電腦需計算的狀況縮減大半, 但以深藍的計算能力, 仍只能計算到 12 步的遊戲樹, 也因此在變化更複雜的圍棋領域, 人腦仍是勝過電腦一籌。

142 特別企劃－電腦如何下棋、玩遊戲？ 除了 Min-Max 演算法外, 在人工智慧的領域仍有許多啟發式 (Heuristics) 的演算法正被研究與應用, 例如近年來相當熱門的基因演算法 (Genetic Algorithm), 配合運算也飛快成長的電腦硬體, 在這個世紀看到機器人大師教小朋友下圍棋也不再只是夢想了。