第 一 章 資料結構導論 課程名稱：資料結構 授課老師： 陳明瑤 2017/9/11.

Presentation on theme: "第 一 章 資料結構導論 課程名稱：資料結構 授課老師： 陳明瑤 2017/9/11."— Presentation transcript:

1 第 一 章 資料結構導論 課程名稱：資料結構 授課老師： 陳明瑤 2017/9/11

2 本章學習目標 讓讀者了解資料結構、演算法及程式之間的關係，以及如何評估演算法的執行效率。
2.讓讀者了解結構化程式設計與物件導向程式設計的差異。 2017/9/11

3 本章內容 1-1 認識資料與資訊的關係 1-2 何謂資料結構？ 1-3 何謂演算法? 1-4 程式設計概念 1-5 結構化程式設計
1-6 物件導向程式設計 1-7 演算法的效率評估 2017/9/11

4 1-1 認識資料與資訊的關係 1.資料(Data)：是指未經過處理的原始記錄，例如學生考試的原始成績。
2.資訊(Information) ：就是有經過處理的結果，例如全班同學成績之排名 及分佈圖。 *資料處理(DP)：是將「資料」轉換成「資訊」的一連串的處理過程。 2017/9/11

5 1.資料(Data) (1)是客觀存在的、具體的、事實的記錄。 (2)簡單來說，日常生活中所記錄的事實資料(姓名、生日、電話及地址)
或學生在期中考的各科原始成績，這些都是未經過資料處理的資料。 如表1-1所示。 2017/9/11

6 2.資訊(Information) (1)經過資料處理之後的結果即為資訊。其資料與資訊的特性比較。 如表1-2所示。 2017/9/11

7 (2)處理程序(例如：成績處理系統)會將原始資料以加整理、計算及分析 之後，變成有用的資訊(含總成績、平均及排名次)。如表1-3 所示。
2017/9/11

8 (3)是決策者在思考某一個問題時所需用到的資料，它是主觀認定的。例 如：班導師(決策者)在學生考完期中考之後，想依學生考試成績來獎
勵，因此，班導師必須要有一份全班排名的成績單(資訊)，以做為獎 勵的依據。 2017/9/11

9 1-2 何謂資料結構？ 「資料結構」(Data Structures)主要是探討如何將資料更有組織地存放到電腦記憶體中，以提昇程式之執行效率的一門學問。 因此，有良好的資料結構（Data structure）及有效率的演算法（Algorithm）將可以大大的提昇程式的執行效率。 2017/9/11

10 程式=資料結構(Data Structure)+演算法(Algorithms) 其中：「資料結構」：是指資料在記憶體中的儲存方式，
在電腦科學(Computer Science)的領域中，我們如何透過電腦來取得即時的、有用的資訊，那就必須先要撰寫有效率及正確的「程式」去運作，而「程式」就是由「資料結構」和「演算法」所構成的。 其公式如下： 程式=資料結構(Data Structure)+演算法(Algorithms) 其中：「資料結構」：是指資料在記憶體中的儲存方式， 「演算法」:則是如何將資料作有效率的處理過程。 因此，當我們在撰寫程式時，只有選擇適當的【資料結構】，才能夠設計出最有效率的【演算法】，進而轉換成為有效率的【程式】。 2017/9/11

11 基本上，資料結構包含有遞迴(Recursive)、陣列(Array)、堆疊(Stack)、佇列(Queue)、串列(List)、樹狀(Tree)、圖形(Graph)、排序(Sort)及搜尋(Search)等單元，雖然這幾種資料結構單元乍看之下，好像非常理論與抽象，但是在我們日常生活中，卻經常可以看到。 2017/9/11

12 遞迴(Recursive)：老鼠走迷宮的問題就是屬於「遞迴」結構。 陣列(Array)：教室座位排列方式就是屬於「陣列」結構。
【舉例】 遞迴(Recursive)：老鼠走迷宮的問題就是屬於「遞迴」結構。 陣列(Array)：教室座位排列方式就是屬於「陣列」結構。 堆疊(Stack)：碗盤的疊法、小朋友排積木、書本裝箱或座電梯等都 具有後進先出的特性就是屬於「堆疊」結構。 佇列(Queue)：排隊買票看球賽，先到先買的方式就是所謂的 「佇列」結構 2017/9/11

13 串列(List)：高鐵火車的車箱串接方式就是屬於「串列」結構。 樹狀(Tree)：如果球賽的賽程方式是採用淘汰制，就是一種「樹狀」結構。
【舉例】 串列(List)：高鐵火車的車箱串接方式就是屬於「串列」結構。 樹狀(Tree)：如果球賽的賽程方式是採用淘汰制，就是一種「樹狀」結構。 圖形(Graph)：當看完球賽要回家的行駛路線圖，則可視為所謂的「圖形」 結構。 排序(Sort)：球賽成績的結果之排名方式就是屬於「排序」結構。 搜尋(Search)：球賽比賽之前找尋某一隊的賽程就是屬於「搜尋」結構。 2017/9/11

14 【老師上課動態展示】 檔案在附書光碟中。 2017/9/11

15 【實例】 撰寫一個程式來計算5位同學的「資料結構」平均成績，並且比較沒有使用資料結構與演算法的差異。 2017/9/11

16 例如：全班學生人數為50人時，則行號04的程式碼就會變數非常的長，
第一種方法沒有使用資料結構與演算法，而是使用一般變數的宣告方式來個別存放成績資料。雖然也可以順利的計算出所需要的結果，但是，比較缺乏彈性，因為，當我們要計算的學生人數異動時，程式將會比較難以維護。 例如：全班學生人數為50人時，則行號04的程式碼就會變數非常的長， 容易產生錯誤。 2017/9/11

17 第二種方法是使用「陣列」資料結構來存放5位同學的成績資料，然後再使用for迴圈的演算法來計算5位同學的成績，最後再列印出結果。
比較分析： 第二種方法的程式比較有彈性，也就是說，當我們要計算的學生人數異動時，只要設定行號01的學生人數及行號05的陣列內容即可。 2017/9/11

18 1-3 何謂演算法? 「演算法」在韋氏辭典中定義為：「在有限步驟內解決數學問題的程
序」。我們可以把演算法(Algorithm)定義成：「解決問題的方法」。 它可以是利用文字敘述、或流程圖或虛擬碼的方式，來表示解決問題的 步驟。 2017/9/11

19 一、撰寫演算法應遵守五點原則： 1.輸入(Input)：不一定要有輸入。可能沒有，也可能是多個資料輸入。
例如(1)：取得系統目前的時間，不須要輸入，只要寫一行now()函數， 就可以輸出系統時間。 例如(2)：求某數為奇偶數時，則必須先要有一個整數輸入，才能進行 判斷。 2017/9/11

20 一、撰寫演算法應遵守五點原則： (續) 2.輸出(Output)：至少一個輸出。 例如：在電腦中，處理資料的基本過程有三個步驟：
輸入 處理 輸出 (原始資料) (程式) (有用的資訊) 所以，使用電腦來為我們處理資料時，有可能是系統自動接收到一個訊號，來當作輸入資料，但是系統至少會輸出一項讓使用者參考的有用資訊。 2017/9/11

21 一、撰寫演算法應遵守五點原則： (續) 3.明確性(Definiteness)：每一行指令都必須明確，不可模稜兩可。
例如：判斷某一數值是否為偶數。 首先我們試著用下列文字來加以描述： 　(1)輸入一個正整數。 　(2)作餘除運算是否為0。 　(3)為0即為偶數。 以上描述看來似乎正確，但是從演算法觀點來看，其中的第(2)點並不符合「明確性」，因它並未說明「餘除運算」是如何運算，容易造成混淆與不解。我們應該改寫為： 　(1)輸入一個正整數N。 　(2)如果N 除以2，其餘數為0。 　(3)則其N為偶數。 不具明確性 具明確性 2017/9/11

22 一、撰寫演算法應遵守五點原則： (續) 例如：
「用功的學生才能領獎學金」就不具有明確性，因為每一個人對用功的定義可能不盡相同，而如果改為「成績90以上的學生才能領 獎學金」就是具有明確性，因為90分是一個比較客觀的定義。 2017/9/11

23 一、撰寫演算法應遵守五點原則： (續) 4.有限性(Finiteness)：演算法不能有無窮迴路，必須能終止執行。
由於演算法並非是真正可以執行的程式，而是設計者所推演出解決問題的步驟，因此，必須在有限的步驟內要完成解決問題的程序。但是，真正的程式是可以有無窮迴路的動作。 例如：Windows 作業系統除非系統關機或當機，否則它會永遠執行一個「等待迴圈」，來等待使用者從鍵盤輸入或其他的輸入設備。 2017/9/11

24 一、撰寫演算法應遵守五點原則： (續) 5.正確性(Correctness) ：既然演算法是解決問題的方法，因此， 正確性是最基本的要求。
例如：以下判斷某數為奇偶數的演算法，雖然符合「明確性」，但是 「不正確」，因為N 除以2，其餘數為0，則N應該為「偶數」， 而非「奇數」。 輸入一個正整數N。 如果N 除以2，其餘數為0。 則其N為奇數。應該改為「偶數」 2017/9/11

25 【日常生活中的例子】 一組可用來解決特定問題的有限指令或步驟，依循這些指令或步驟，可以進行解題。食譜 - 做蛋糕
2017/9/11 圖片來源： /cornliu/cornppt/第六章.ppt

26 輸 入 明確性 有限性 輸 出 正確性 好吃的蛋糕怎麼來?
輸　入 明確性 有限性 輸　出 正確性 2017/9/11 圖片來源： /cornliu/cornppt/第六章.ppt

27 二、描述演算法有三種方法： (一)文字敘述
演算法可用文字加以描述，但是採用口語化的文字敘述來加以描述，其缺點在於冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較不常用。 例如：請利用「文字敘述」使用者登入帳號與密碼時，系統檢查的過程。 步驟一：輸入使用者帳號與密碼 步驟二：判斷帳號與密碼是否正確 步驟三：如果正確時，則可以登入系統 否則，就無法登入！ 2017/9/11

28 (二)流程圖（Flowchart） 『流程圖』是指利用圖形方式來表達欲解決問題的步驟。當我們想利用電腦程式語言來處理問題時，先要了解問題並想出許多方案來解決問題，並且分析那些資料是要「輸入」，經過「處理」之後，要「輸出」那些結果。 2017/9/11

29 2017/9/11

30 2017/9/11

31 【舉例】 請繪出使用者登入帳號與密碼時，系統檢查的流程圖。 2017/9/11

32 虛擬碼兼具文字描述及流程圖的優點，其方式是用文字摻雜程式語 言，來描述解題步驟與方法。
(三)虛擬碼（Pseudo Code） 虛擬碼兼具文字描述及流程圖的優點，其方式是用文字摻雜程式語 言，來描述解題步驟與方法。 例如1：請利用「虛擬碼（Pseudo Code）」敘述使用者登入帳號與密碼時，系統檢查的過程。 (1)Input: UserName, Password (2)IF (UserName And Password) ALL True Output: You Can Pass! else Output: You Can not Pass! 2017/9/11

33 (2)Total=Total+Count; (3)Count=Count+1;
例如：1+2+3+…+10虛擬碼可以描述如下： (1)設Count=1,Total=0; (2)Total=Total+Count; (3)Count=Count+1; (4)若Count > 10 則至步驟(5)，否則回步驟(2) (5)印出Total 2017/9/11

34 1-4 程式設計概念 我們要開始程式設計時，一定要進行下面五個步驟： 2017/9/11

35 2017/9/11

36 2017/9/11

37 〔實例〕 計算國文與英文的平均成績，並依照平均成績來求顯示「及格」與「不及格」。 1.分析及定義問題。 兩個等級分別如下：
(1)及格：60(含)以上。 (2)不及格：60以下。 2.畫出整合問題的流程圖或撰寫問題的演算法。 2017/9/11

38 3.撰寫及建立程式模組。 2017/9/11

39 4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止。
當使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績為60.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態改為Single(單精準度) 2017/9/11

40 【重要觀念】 系統發展的生命週期與程式設計之步驟比較 2017/9/11

41 1-4.1 演算法與程式的差異？ 1.「演算法」是以「人」為主，亦即「任何人都可以閱讀的程式碼」， 因此，必須特別強調「可讀性」。
2.「程式」則是以「電腦」為主，它強調程式的執行結果正確性、可維護 性及執行效率。 2017/9/11

42 1-4.2為什麼要撰寫程式? 我們為什麼要花那麼多時間來撰寫程式呢？其主要的目的：它可以快速解決「複雜的問題」。
甲同學說：請電腦幫我計算1加到10的總合。 或許你會認為這簡單的問題，你我都會算，何必寫程式呢？ 但是，如果甲同學又說：請電腦幫我計算1加到50000時，我想我們就無法馬上計算出結果。由上面的例子，我們可以非常清楚的知道，程式語言幫忙人類解決複雜的問題。 2017/9/11

43 1-5 結構化程式設計 何謂結構化程式設計呢？它是利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組。如圖1-5所示。
1-5 結構化程式設計 何謂結構化程式設計呢？它是利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組。如圖1-5所示。 圖1-5 結構化程式設計的示意圖 2017/9/11

44 結構化程式設計由Dijkstra (1969)提出： 1. 消除程式因goto而造成如麵條式的混亂狀態。
2. 強調任何程式邏輯均可由三種結構組成。如圖1-6所示。 (1)循序(Sequence)：簡單命令式的指令如 COMPUTE, READ, WRITE 與代數指令如X=Y+Z。 (2)選擇(Condition)：需做決策時，用 IF-THEN-ELSE 指令與 CASE 指令。 (3)重複(Repetition)：當需反覆時，用 DO-WHILE 與 DO-UNTIL 指令。 2017/9/11

45 2017/9/11

46 1-5.1 循序結構 所謂循序結構，是指程式由上而下，依序逐一執行。亦即『程式碼被執行的順序為由上而下，一個敘述接著一個敘述依序執行』。此種結構是最基本的結構。如圖1-7所示： 2017/9/11

47 選擇結構 如果只希望在某種條件成立時才執行某些敘述，而某種條件不成立才執行另一種敘述，來過濾一些條件。那我們就必須使用「選擇結構」的方式了。如圖1-8所示。 2017/9/11

48 此種結構是最常被使用的方式，因為大部份的選擇結構的情況 可能是兩種。 例如：判斷及格與不及格、判斷奇數與偶數、判斷男生與女生
…等情況，都可以利用此種結構來完成。 2017/9/11

49 其中(條件式) 是一關係運算式 或 邏輯運算式 2.說明：如果「條件式」成立(真)，就執行 Then後面的「敘述區塊1」
1.語法： 其中(條件式)  是一關係運算式 或 邏輯運算式 2.說明：如果「條件式」成立(真)，就執行 Then後面的「敘述區塊1」 ，否則就執行「敘述區塊2」。 3.使用時機：當條件只有二種情況時最佳方法。 2017/9/11

50 5. 流程圖：如圖1-9所示： 2017/9/11

51 重複結構 在處理一再重複的相同動作，這對電腦而言，是一件非常Easy的事，但對我們人類而言卻是一件苦差事，因此驅使電腦做這樣的事情的方式，就是迴圈(Loop)，亦即讓某一段程式反覆執行多次的敘述，我們稱此結構為「迴圈結構」。 2017/9/11

52 如果我們想要撰寫一段程式，來輸出1,2,…,100時，怎麼辦？目前最少有兩種方法可以使用。如圖1-10所示：
2017/9/11

53 1-6 物件導向程式設計(選讀) 物件導向設計是以「物件」為主，首先規劃整個系統需要那些物件，再分析這些物件有什麼特性(屬性)、如何操作(方法)，以及物件與物件之間的關連性，然後開始撰寫各個物件模組，最後再依照系統的需求，將各個封裝良好的物件模組由下向上架構出整個系統。 2017/9/11

54 每一個物件模組就是一個定義好的類別，其內容包括一些私有的資料項目和功能(即屬性)，以及供外界來操作的一些方法。如圖1-11所示。
2017/9/11

55 1-6.1 物件導向的基本觀念 「物件導向」可以說是現代最新的一種思考方式，而每一個物件都具有其特有的屬性(Attribute)及行為(Behavior)及方法(Method)，並且可以是一個抽象物、觀念、概念、或是一個有明確界定範圍的事物。 2017/9/11

56 一、何謂物件(Object) 何謂物件？ 簡單的說，物件就是「東西」。 日常生活中，看得到、摸得到、感覺得到的都是物件。任何東西都可以當作物件，像人也可以當作一個物件，每個人(物件)都有它的特性(屬性)，包括：身高、體重、性別、年齡…等描述。因此，我們就可以區別出人與人之間的不同之處。然而小物件還可以再組成一個大物件，例如：車子是一個大物件，它是由四個輪子、四個車門、方向盤…等其他小物件所組成的。 2017/9/11

57 若以電腦世界來說，VB設計模式中的「工具箱」之所有元件，其實都可以當作「物件」，而這物件就是撰寫程式時的重要「零件」，我們可以把它當成是在堆積木一般的排列組合，進一步的設計屬於自己的程式。我們可以將下圖中的小算盤應用程式視為一個大物件，它是由數個按鈕、一個文字方塊及功能表的小物件所組成的。 2017/9/11

58 2017/9/11

59 2017/9/11

60 二、何謂屬性(Property) 屬性可以說是物件的性質，是用來區分不同的物件。例如每一個「人」都具有「髮色」、「身高」、「體重」、「性別」…等不同的屬性。而屬性的內容稱為「屬性值」，如人的「性別」屬性之屬性值有「男與女」兩種情況，因此我們就可以區分出不同性別的人，如圖1-13所示： 2017/9/11

61 每一個人(物件)都有他們的姓名、身高、性別及外貌等等，這些都是他們的屬性。每一個人一定會有這樣屬性，但是每一個人可能都有不同的屬性值，也就是說小明與小華的姓名、身高、體重、性別及外貌有可能皆不相同，就是因為如此，我們才能分辨出小明與小華的不同點。 2017/9/11

62 2017/9/11

63 因此，我們在撰寫物件導向的程式時，我們可以藉由改變屬性的屬性值，即可改變物件的外觀。而改變屬性的方法有二種：
第一種：靜態設定(在「屬性」視窗的對話方塊中設定)。如圖1-15所示：在設計階段時，在該物件的屬性視窗直接設定之，馬上顯示效果。 2017/9/11

64 第二種：動態設定(在程式碼視窗的程序中撰寫)。如圖1-16所示： 物件名稱和屬性名稱中間使用點號加以區隔。
2017/9/11

65 二、何謂事件(Event) 所謂事件？可說是一種被動性的動作或某一情境下所產生的行為。例如：當小孩被父母「打」時，他的反應動作是「手痛得跳起來」，並發出「尖叫」的聲音，連下來可能「開始哭」。綜合上述，小孩被父母「打」是一種「事件」，當這個事件被啟動之後，小孩便產生了一連串的動作：「手痛得跳起來」、「尖叫」、「開始哭」…等動作，稱為「事件程序」，通常物件會具備設許多個「事件」，我們只要在必要的事件中，指定其動作即可。 事件是一種加在物件上的「作用」，而事件程序則是物件對此作用所產生的「反應」。事件程序的表達方式。 2017/9/11

66 2017/9/11

67 四、何謂方法(Method) 所謂「方法」，是指為了在物件完成某件事或達成某項目標，所採取的處理方式。物件原來內含的函數或程序就叫做方法。物件的「屬性」或「事件程序」都可以重新設定或修改，但是「方法」的內容是固定、不能修改的。在VB中，物件與方法的表達方式為： 2017/9/11

68 例如，在表單物件中提供了清除、列印、畫點、畫線、…等功能，這些功能通稱為「方法」。 譬如，我們想要將表單中的TextBox文字框內容清除，只要撰寫TextBox1.Clear( )即可。
2017/9/11

69 物件導向程式設計的特性 物件導向程式設計的最主要精神就是物件，但是支援物件的程式語言並不一定是物件導向程式語言(例如VB6.0)，它只是一種以物件為基礎的程式語言（Object-based Languages），亦即提供物件觀念。而VB.NET、Visual Basic 2005、C#、C++及Java才是真正的物件導向程式語言。 物件導向主要是由四個基礎概念所構成，分別為封裝性(Encapsulation)、抽象化(Abstraction)、繼承性(Inheritance)及多型(Polymorphism)這四個觀念。 2017/9/11

70 一、封裝性(Encapsulation)
封裝性就是將物件的「屬性」與「操作」或「方法」一起封裝到類別中。 這是一種資訊隱藏（information hiding）的概念。因此，可以提供安全 性，因為物件的狀態無法被外界直接控制；另一方面，介面可以簡化對於 物件狀態的了解，因為外界不必了解物件狀態的細節。如圖1-18所示。 2017/9/11

71 例如以電視機來說明封裝性的概念：如圖1-19所示。
在日常生活中的“電視機”提供給使用者的是螢幕和一組功能按鈕，使用者透過對這組「功能按鈕」的操作和「螢幕」來觀賞電視節目，而使用者不必知道電視機是如何實作這些功能的。因為電視機把選擇頻道、控制音量、調整色彩、對比度和亮度等功能的實作都「封裝」起來了，以避免使用者任意破壞。 2017/9/11

72 二、繼承性(Inheritance) 繼承性就是物件可以繼承其他物件的「屬性」及「操作」。例如兒子繼承爸爸或媽媽的特色(屬性或方法)，且兒子會再擁有自己新的特色。繼承性的目的是增加再用性，避免了屬性及操作的重複。被繼承的類別可稱為「父類別(parent class)」、「超類別(supperclass)」或「基底類別(base class)」，而 繼承的類別可稱為「子類別(child class)、「次類別(subclass)」或「衍生類別(derived class)」。 2017/9/11

73 例如：當我們將各物件抽象化為「交通工具」類別後，我們可以再依 據物件導向的「繼承性」之特性，將交通工具再細分為陸上交
通工具、水上交通工具、空中交通工具等三個類別。如圖1-20 所示。 2017/9/11

74 三、抽象化(Abstraction) 在真實世界中，我們可以把汽車當作是一個物件，也可以把貨車、吉普車等當作是一個物件，若我們沒有從抽象化的觀點來看待這些物件時，則會發現這個世界將會充滿無數的類似物件，使我們會不知如何去了解它們。但若透過「抽象化」觀念來剔除物件間的差異，則我們可以將這些物件抽象化為「交通工具」這個類別。如圖1-21所示。 2017/9/11

75 四、多型性(Polymorphism) 多型的概念常以一句話來解釋：「一個介面，多個方法」。這代表有可能可以設計一個通用的介面給一組相關動作。亦即同一個名稱的操作,在不同的類別當中表示不同的行為。例如，父類別(Super Class)中有一個名叫做 show() 的方法，用來顯示學生的姓名資料，子類別中也有一個名叫 show() 的方法，用來顯示學生的成績資料，這二個方法都稱為 show()。 2017/9/11

76 2017/9/11

77 1-7 演算法的效率評估 演算法的效率評估指的是用來計算某些演算法所撰寫的程式在經過編譯之
1-7 演算法的效率評估 演算法的效率評估指的是用來計算某些演算法所撰寫的程式在經過編譯之 後實際執行所需要的時間。但是，實務上有可能因為程式編譯的過程或是 電腦設備的差異使得效率分析會因電腦的軟硬體不同而有不同的結果，因 此，一般而言，效率的評估方式可分為兩大類： 一、時間複雜度（Time Complexity） 二、空間複雜度（Space Complexity） 2017/9/11

78 一、時間複雜度（Time Complexity）
是指從呼叫該副程式開始到完成之過程，所有花費的執行時間。 基本上，影響程式執行時間的因素，有種兩因素： 1. 演算法效率的好壞 2. 機器的CPU執行速度 所以，執行時間=執行次數 * 每次執行所需的時間。 2017/9/11

79 由於每一行程式所需的時間必須考慮到機器本身的CPU執行速度及編譯器的功能，所以，在評估上比較不客觀。因此，通常只考慮執行的次數，所以，在相同功能的條件之下，執行次數的多寡，往往是用來決定演算法效率的好壞。也就是說，我們必須先計算出程式中每一敘述的執行次數，再一一的加總起來，然後再求出其Big-O。 例如：計算下列程式中變數Count被執行的次數為何？ 2017/9/11

80 二、空間複雜度（Space Complexity）
是指從呼叫該副程式開始到完成之過程，所有佔用的記憶體空間。 例如：參數、變數宣告，回傳值以及傳回位址時，都會佔用記憶體空間。 2017/9/11

81 2017/9/11

82 ◆時間複雜度與空間複雜度之分析 基本上，時間複雜度的分析比空間複雜度來得重要，因為當資料量龐大時，時間複雜度會有較大的差異性，但是，空間複雜度則差異較小，再加上目前的記憶體相當便宜，因此，目前在資料結構所探討演算法之效率評估，都著重在時間複雜度方面的評估。 2017/9/11

83 1-7.1 時間複雜度(Time complexity)
【舉例1】假設有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加，請問程式的執行次數為何？ 【解析】行號04會執行n+1次，而前n次會執行迴圈主體，但是在第n+1次時 沒有符合迴圈的條件，故離開迴圈。 2017/9/11

84 【舉例2】假設兩矩陣a, b相加，並且矩陣大小皆為n*n，請計算出下列程式的執行次數。
【解析】行號04外層迴圈(for)的計數器i從0~n-1，共會執行n+1次，而行號05內層迴圈(for)的計數器j從0~n-1，也會執行n+1次。因此，當外層迴圈執行1次時，則內層迴圈要執行一回合，也就是j從0~n-1(共有n次) 2017/9/11

85 【舉例3】假設兩矩陣a, b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執行次數。
2017/9/11

86 在經過上面例子，來算出程式敘述的執行次數後， 我們雖然可以利用理論「上下限Θ(n)」比理論上限O(n)與理論下限Ω(n)都來得準確，但是在通常利用理論上限O(n)之Big-O來表示此演算法的執行時間，亦稱為該程式的「時間複雜度(time complexity)」。 2017/9/11

87 一、O(n)( Big-O of n)的定義： 最常被使用，用來表示理論「上限」
O(n)可視為某演算法在電腦中所需執行時間，亦即某演算法的執行時間T(n)的時間複雜度(time complexity)為O(n)(讀成Big-O of n)。 【Big-O的觀念】 Big-O取執行次數中最高次方或最大指數部份的項目即可。 如： 陣列元素相加為2n+3 = O(n) 矩陣相加為2n2+2n+2 = O(n2) 矩陣相乘為2n3+4n2+2n+2 = O(n3) 2017/9/11

88 因此，透過時間複雜度分析之觀念，我們就可以判斷某些程式的執行效率是否良好。
【假設】 f(n)：統計的執行次數。 g(n)：Big-O取執行次數中最高次方或最大指數部份的項目。 f(n)=O(g(n))，若且唯若，存在一正整數c及n0，對所有的n，nn0時，則f(n)c*g(n)。 2017/9/11

89 1.f(n)就會等於2n2+2n+2 亦即： f(n)= 2n2+2n+2 2.g(n)則取f(n)中的最高次方 亦即：g(n) =n2
∴ f(n)=O(g(n)) 2017/9/11

90 2017/9/11

91 2017/9/11

92 二、Ω(n) (Omega of n)定義： 用來表示理論「下限」
f(n)=(g(n))，若且唯若，存在正整數c及n0，對所有的n，nn0時， 則f(n)c*g(n)。 2017/9/11

93 2017/9/11

94 三、Θ(n)( Theta of n)定義： 表示理論上限與下限均為此函數
是一種比Big-O與Ω更精確時間複雜度的漸近表示法。 f(n)=(g(n))，若且唯若，存在正整數c1、c2及n0，對所有的n，nn0時，則c1*g(n )  f(n)  c2*g(n)。 2017/9/11

95 2017/9/11

96 四、時間複雜度的等級 若n代表資料的數量，時間複雜度可分為下列不同的等級： 2017/9/11

97 2017/9/11

98 1-7.2 空間複雜度(Space Complexity)
一個程式P的空間複雜度(Space Complexity)包含固定的空間需求與變 動的空間需求兩個部分。 一、固定的空間需求 包含了程式在編譯時期(Compile Time)所產生的空間需求。例如程式本身的指令空間、常數、靜態變數及結構等。 二、變動空間需求 包含了動態記憶體要求(Dynamic Memory Allocation)所配置的空間，以及遞迴函數執行時所需要用來儲存活動紀錄(Activation Record)的執行時堆疊空間(Run Time Stack)。 2017/9/11

99 通常我們會利用S(P)來表示一個程式P所需的空間需求， 公式：S(P)=c+SP(I) 其中： c代表這個程式的固定空間需求
SP(I)則表示程式P針對特定的輸入資料集合I (Instance) 所需的變動空間需求。 2017/9/11

100 【實例】試”著計算出三個整數之平均”的空間複雜度為何？
【解答】 在上面的例子中，Add函數有3個參數及1個傳回值，因此，固定的空間需求為(3+1)*2bytes=8bytes，而Add函數並沒有使用到動態配置記憶體，所以，變動空間需求為0byte，因此，空間複雜度的需求為8+0=8bytes 2017/9/11

101 1-7.3 演算的效率分析-排序演算法的比較 2017/9/11

102 1-7.4 常用的數學式子 2017/9/11

103 2017/9/11