課程名稱：資料結構 授課老師：_____________

Presentation on theme: "課程名稱：資料結構 授課老師：_____________"— Presentation transcript:

1 課程名稱：資料結構 授課老師：_____________
第 一 章 資料結構導論 課程名稱：資料結構 授課老師：_____________

2 本章學習目標 讓讀者了解資料結構、演算法及程式之間的關係 讓讀者了解如何評估演算法的執行效率。

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

4 1-1 認識資料與資訊的關係 1.資料(Data)：是指未經過處理的原始記錄。 例如：學生考試的原始成績。
2.資訊(Information) ：就是有經過「資料處理」的結果。 例如：全班同學成績之排名及分佈圖。 資料處理(Data Processing)則是將「資料」轉換成「資訊」的一連串 處理過程，而這一連串的處理過程就是透過「程式」來處理。 例如：成績處理系統。如下圖所示：

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

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

7 (2)「資料處理」會將原始資料以加整理、計算及分析之後，變成有用
的資訊(含總成績、平均及排名次)。 如表1-3 所示。

8 (3)有用的資訊是決策者在思考某一個問題時所需用到的資料，它是主觀
認定的。例如：班導師(決策者)在學生考完期中考之後，想依學生考 試成績來獎勵。

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

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

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

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

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

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

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

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

17 1-3 何謂演算法? 「演算法」在韋氏辭典中定義為：「在有限步驟內解決數學問題的程
序」。我們可以把演算法(Algorithm)定義成：「解決問題的方法」。 【題目】製作蛋糕的方法，其步驟如下：

18 1-3.1撰寫演算法應遵守五點原則 1.輸入(Input)：不一定要有輸入。可能沒有，也可能是多個資料輸入。
【題目】 製作蛋糕時，必須要輸入：「雞蛋、麵粉及鮮奶」等食材。

19 【課本例子】 例如1：不需輸入 如果想要取得系統目前的時間，不須要輸入，只要寫一行now() 函數，就可以輸出系統時間。 例如2：必需輸入
求某數為奇偶數時，則必須先要有一個輸入整數，才能進行 判斷。

20 一、撰寫演算法應遵守五點原則： (續) 2.明確性(Definiteness)：每一行指令都必須明確，不可模稜兩可。
【題目】製作蛋糕時，要加入多少的麵粉與雞蛋及要加熱多久， 必須明確，不可模稜兩可。

21 【課本例子】 例如1：判斷某一數值是否為偶數。 首先我們試著用下列文字來加以描述：
　(1)輸入一個正整數。 　(2)作餘除運算是否為0。 　(3)為0即為偶數。 以上描述看來似乎正確，但是從演算法觀點來看，其中的第(2)點並不符合「明確性」，因它並未說明「餘除運算」是如何運算，容易造成混淆與不解。我們應該改寫為： 　(1)輸入一個正整數N。 　(2)如果N 除以2，其餘數為0。 　(3)則其N為偶數。 不具明確性 具明確性

22 【課本例子】 例如2： 「用功的學生才能領獎學金」就不具有明確性，因為每一個人對用功的定義可能不盡相同，而如果改為「成績90以上的學生才能領
獎學金」就是具有明確性，因為90分是一個比較客觀的定義。

23 一、撰寫演算法應遵守五點原則： (續) 3.有限性(Finiteness)：演算法不能有無窮迴路，必須能終止執行，
亦即必須在有限的步驟內完成。 【題目】製作蛋糕必須在有限的步驟內完成

24 【課本例子】 由於演算法並非是真正可以執行的程式。但是，真正的程式是可以有無窮迴路的動作。
例如：Windows 作業系統(系統程式)除非系統關機或當機，否則它會 永遠執行一個「等待迴圈」，來等待使用者從鍵盤輸入或其他 的輸入設備。

25 一、撰寫演算法應遵守五點原則： (續) 4.正確性(Correctness) ：既然演算法是解決問題的方法，因此， 正確性是最基本的要求。
【題目】製作出來的蛋糕必須要正確，亦即符合使用者的需求

26 【課本例子】 例如：以下判斷某數為奇偶數的演算法，雖然符合「明確性」，但是 「不正確」，因為N 除以2，其餘數為0，則N應該為「偶數」，
而非「奇數」。 輸入一個正整數N。 如果N 除以2，其餘數為0。 則其N為奇數。應該改為「偶數」

27 一、撰寫演算法應遵守五點原則：( 續) 5.輸出(Output)：至少一個輸出。
【題目】在製作蛋糕時，在輸入「雞蛋、麵粉及鮮奶」之後，一定會有輸出。

28 【課本例子】 例如：在電腦中，處理資料的基本過程有三個步驟： 輸入 處理 輸出 (原始資料) (程式) (有用的資訊)
輸入 處理 輸出 (原始資料) (程式) (有用的資訊) 所以，使用電腦來為我們處理資料時，有可能是系統自動接收到一個訊號，來當作輸入資料，但是系統至少會輸出一項讓使用者參考的有用資訊。 2017/3/8

29 1-3.2 描述演算法有三種方法 (一)文字敘述 【定義】演算法可用文字來加以描述，但是會比較不精確，因此一般較 不常用。 【題目】
描述演算法有三種方法 (一)文字敘述 【定義】演算法可用文字來加以描述，但是會比較不精確，因此一般較 不常用。 【題目】 請利用「文字敘述」來描述使用者登入帳號與密碼時，系統檢查的過程。 【解答】 步驟一：輸入使用者帳號與密碼 步驟二：判斷帳號與密碼是否正確 步驟三：如果正確時，則可以登入系統 否則，就無法登入！

30 (二)流程圖（Flowchart） 【定義】利用圖形方式來表達欲解決問題的步驟。 【題目】 請利用「流程圖」來描述使用者登入帳號與密碼時，系統檢查的過程。 【解答】 說明：流程圖可以協助程式設計者設計程式，可增加程式的可讀性。

31 (三)虛擬碼（Pseudo Code） 【定義】兼具文字描述及流程圖的優點，其方式是用文字摻雜程式語言， 來描述解題步驟與方法。 【題目】 請利用「虛擬碼」敘述使用者登入帳號與密碼時，系統檢查的過程。 【解答】 (1)Input: UserName, Password (2)IF (UserName And Password) ALL True Output: You Can Pass! else Output: You Can not Pass! 說明：在資料結構中，一般都是利用「虛擬碼」來表示演算法。

32 延伸學習<觀念> 一、流程圖（Flowchart） 【定義】利用圖形方式來表達欲解決問題的步驟。
【優點】1.它可協助程式設計者設計更周詳的程式 2.可增加程式的可讀性 3.對於初學者而言可幫助奠定良好的程式設計基礎 【作法】分析那些資料是要「輸入」，經過「處理」之後，要「輸出」 那些結果。 【繪製原則】 1.流程圖必須使用標準符號，便於閱讀和分析。 2.流程圖中的文字力求簡潔、扼要，而且明確可行。 3.繪製方向應由上而下，由左至右。 4.流程線條避免太長或交叉，可多用連接符號。

33 延伸學習<練習> 一、流程圖（Flowchart）<續>
【舉例】請繪出使用者登入「帳號」與「密碼」時，系統檢查的流程圖。 提示： 步驟1：輸入帳號與密碼 <輸入> 步驟2：檢查是否正確 <處理> 步驟3.1：正確時，則顯示Pass。 <輸出> 步驟3.2：不正確時，則顯示NoPass。 <輸出>

34 延伸學習<比較> 二、虛擬碼（Pseudo Code）【比較「流程圖」與「虛擬碼」】
【題目】比較1+2+3+…+10的「流程圖」與「虛擬碼」。 (1)設Count=1,Total=0; (2)Total=Total+Count; (3)Count=Count+1; (4)若Count <=10 則回步驟(2) (5)印出Total

35 1-4 程式設計概念 我們要開始程式設計時，一定要進行下面五個步驟： 步驟1. 分析所要解決的問題(需求) 說明：
1-4 程式設計概念 我們要開始程式設計時，一定要進行下面五個步驟： 步驟1. 分析所要解決的問題(需求) 說明： (1)首先要瞭解問題的需求及條件。 (2)確定要輸入那些資料。 (3)確定要輸出那些資訊報表。

36 1-4 程式設計概念(續) 步驟2. 設計解題的步驟(演算法) 說明： 撰寫演算法可以利用(1)文字敘述(2)流程圖(3)虛擬碼來表示
1-4 程式設計概念(續) 步驟2. 設計解題的步驟(演算法) 說明： 撰寫演算法可以利用(1)文字敘述(2)流程圖(3)虛擬碼來表示 解決問題的步驟。

37 1-4 程式設計概念(續) 步驟3. 編寫程式 (程式碼) 說明： 選擇適當的程式語言，將演算法的步驟寫成一個完整的程式。

38 1-4 程式設計概念(續) 步驟4. 上機測試、偵測錯誤 (偵錯) 說明：
1-4 程式設計概念(續) 步驟4. 上機測試、偵測錯誤 (偵錯) 說明： 一個「有用性」及「易用性」的程式，必須要經過多次的測試，若有錯誤，立即更正，直到正確無誤為止。

39 1-4 程式設計概念(續) 步驟5. 編寫程式說明書(可執行) 說明：
1-4 程式設計概念(續) 步驟5. 編寫程式說明書(可執行) 說明： 一個功能強而完整的程式，使用者就會願意使用，因此必須有使用說明書，以便於別人使用或日後的維護。

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

41 題目：計算平均成績，並判斷是否及格 3.撰寫及建立程式模組 01 02 03 04 05 06 07 08 09 10 11 12
Procedure Method( ) Begin int C_Score, E_Score, Average; C_Score=60; E_Score=70; Average = (C_Score + E_Score) / 2; if (Average >= 60) printf("及格"); else printf ("不及格"); End End Procedure

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

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

44 1-4.1 演算法與程式的差異？ 1.「演算法」是以「人」為主，亦即「任何人都可以閱讀的程式碼」， 因此，必須特別強調「可讀性」。

45 1-4.1 演算法與程式的差異？(續) 2.「程式」則是以「電腦」為主，它強調程式的執行結果正確性、 可維護性及執行效率。

46 1-4.2為什麼要撰寫程式? 主要的目的：快速解決「複雜的問題」。 例如1：小華問：小明請幫我計算1加到10的總和。
小明說：1+2+3+…+10=55大家都會，太簡單了！

47 1-4.2為什麼要撰寫程式?(續) 例如2： 小華又問：小明請幫我計算1加到50000時。
小明則說：太困難了，我無法馬上計算出結果。但是我可以利用 「撰寫程式」來處理。 說明：因此，我們可以非常清楚的知道，程式語言幫忙人類 「解決複雜的問題」。

48 1-4.3 一個好程式需要滿足條件 一、正確性(Correctness) 二、效率性(Performance)
三、可維護性(Maintainable)

49 一、正確性(Correctness) 既然演算法是解決問題的方法，所以正確性是一個好程式最基本的要求。 例如：設計一個判斷奇偶數的程式
說明：上面的程式處理過程中，由於程式不正確，所以產生錯誤的結果。

50 二、效率性(Performance) 指程式真正執行時所必須要花費的時間。一般評估執行時間是依程式碼所被執行的總次數來計算。亦即所謂的「頻率次數)」當頻率次數愈高時，代表所需的執行時間愈長。 例如：計算下列程式中變數Count被執行的次數為何？

51 三、可維護性(Maintainable)
一個好的程式，不只需要有效率地被正確地執行之外，也必須要考慮程 式的可讀性、及未來修改和擴充性，這屬於程式設計方法和風格的問題， 例如：使用模組化來設計程式和加上完整程式註解的說明。

52 三、可維護性(Maintainable)(續)
(一) 縮排 【使用時機】在使用巢狀結構時，必須特別需要。 使用「縮排」技巧 未使用「縮排」技巧

53 三、可維護性(Maintainable)(續)
(二) 註解 【定義】它是一種「非執行的敘述」亦即是給人看的，而電腦不會去執 行它。此功能就是用來說明某一段程式碼的作用與目的。 1.使用雙斜線「//」的使用時機：可以寫在程式碼的後面或單獨一行註解。 2.使用「/*……*/」的使用時機：註解的內容超過一行時。

54 三、可維護性(Maintainable)(續)
(三) 變數及函數名稱的命名 好的變數宣告命名 說明：爾後維護時，看到變數名稱就可以得知變數的意義。 不好的變數宣告命名 說明：爾後維護時，無法馬上得知A與B變數所代表的意思。

55 1-5 結構化程式設計 【定義】利用「由上而下」的技巧，將程式分解成許多個獨立功能的 模組。如圖1-5所示。
1-5 結構化程式設計 【定義】利用「由上而下」的技巧，將程式分解成許多個獨立功能的 模組。如圖1-5所示。 圖1-5 結構化程式設計的示意圖

56 每一個獨立功能的模組都是由結構化程式設計的三個基本結構所組成。

57 1-5.1 循序結構 【定義】是指程式由上而下，依序逐一執行。 【題目】計算國文與英文兩科的平均成績。如下圖所示：

58 選擇結構 【定義】指根據某種條件成立，來選擇不同的執行路徑。 【題目】計算兩科平均成績，並判斷平均成績是否及格。如下圖所示。

59 1-5.3 重複結構 【定義】指讓某一段程式反覆執行多次的敘述。 【題目】利用迴圈來計算兩科總分及平均。如圖1-8所示。 i<=2
重複結構 【定義】指讓某一段程式反覆執行多次的敘述。 【題目】利用迴圈來計算兩科總分及平均。如圖1-8所示。 i<=2 重複結構 i++

60 1-6 演算法的效率評估 【定義】指用來計算某些演算法所撰寫的程式，在經過編譯之後， 實際執行所需要的時間。 【評估方法】
1-6 演算法的效率評估 【定義】指用來計算某些演算法所撰寫的程式，在經過編譯之後， 實際執行所需要的時間。 【評估方法】 一、時間複雜度（Time Complexity） 二、空間複雜度（Space Complexity）

61 一、時間複雜度（Time Complexity）
【定義】 是指從主程式呼叫該副程式開始到完成之過程，所有花費的 「執行時間」。

62 執行時間=執行次數 【影響執行時間因素】 (1) 硬體部份：機器的CPU執行速度不考慮
(2) 軟體部份：演算法的好壞是由執行時間來決定，因此， 執行時間 = 執行次數╳每次執行所需時間 但是，由於每次執行所需時間會受CPU的影響(所以不考慮，則設為常數1)，所以： 執行時間 = 執行次數╳ 1 因此， 執行時間=執行次數

63 二、空間複雜度（Space Complexity）
【定義】是指從主程式呼叫該副程式開始到完成之過程，所有佔用的 「記憶體空間」。例如：參數、變數宣告，回傳值以及傳回 位址時，都會佔用記憶體空間。 說明：保存A函數當時執行時之狀態 包括：參數值區域變數值返回位址(Return Address)，

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

65 1-6.1 時間複雜度(Time complexity)
【定義】 是指計算執行程式所花費的時間。一般而言，我們可以將一個程式P的時間複雜度表示成T(P)的形式。而T(P)記錄了程式執行次數n的成長速率。

66 一、演算法的「執行次數」 【定義】一般評估執行時間是依程式碼所被執行的總次數來計算。 也就是所謂的「頻率次數)」，當頻率次數愈高時，代表所
需的執行時間愈長。 【題目1】 假設有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加， 請問程式的執行次數為何？ 題目：陣列元素相加之演算法 【解答】執行的次數 01 02 03 04 05 06 07 int sum(int a[ ], int n) { int i, total=0; for (i=0; i <n; i++) total += a[i]; return total; } 1 n+1 n T(P)=2n+3 加 總 i會再多執行 1次的比較

67 假設兩矩陣a, b相加，並且矩陣大小皆為n*n，請計算出下列程式的執行次數？
【題目2】 假設兩矩陣a, b相加，並且矩陣大小皆為n*n，請計算出下列程式的執行次數？ 題目：兩矩陣a, b相加，利用雙重迴圈演算法 【解答】執行的次數 01 02 03 04 05 06 07 void Add(int a[,], int b[,], int c[,], int n) { int i, j; for(i=0; i<n; i++) for (j=0; j<n; j++) c[i,j] =a[i,j]+b[i,j]; } 1 n+1 n*(n+1) n2 T(P)=2n2+2n+2 加 總

68 假設兩矩陣a, b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執行次數？
【題目3】 假設兩矩陣a, b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執行次數？ 題目：兩矩陣a, b相乘，利用多重迴圈演算法 【解答】執行的次數 01 02 03 04 05 06 07 08 09 10 11 12 void Multi(int a[,], int b[,], int c[,], int n) { int i, j, k, sum; for (i=0; i <n; i++) for (j=0; j < n; j++) sum = 0; for (k=0; k < n; k++) sum = sum+a[i,k]*b[k,j]; c[i,j] = sum; } 1 n+1 n*(n+1) n2 n2*(n+1) n3 T(P)=2n3+4n2+2n+2 加 總

69 【練習題】 假設有一個巢狀迴圈之演算法，如下所示： 請追蹤x=x+1的總執行次數？ 【解答】 ∴利用等差數列： 演算法
For i=1 to n do For j=i to n do x=x+1 End 演算法 統計執行的次數 For i=1 to n do For j=i to n do x=x+1 End i= i= i= …… i=n j=1 to n j=2 to n j=3 to n …… j=n to n 執行：n次 (n-1)次 (n-2)次 …… 次

70 二、演算法的「時間複雜度O(n)」 【定義】O(n)可視為某演算法在電腦中所需執行時間，亦即將 「執行次數」轉換成電腦所需的執行時間。
【執行次數轉換時間複雜度之作法】 取「執行次數」中最高次方或最大指數部份的項目即可。 陣列元素相加為2n+3 = O(n) 矩陣相加為2n2+2n+2 = O(n2) 矩陣相乘為2n3+4n2+2n+2 = O(n3)

71 三、時間複雜度的等級 【定義】在資料結構中，評估某一演算法的執行效率，必須視其 時間複雜度的等級。 【時間複雜度的等級】
O(n)比O(n2)更有效率 說明：效率愈高，代表著執行時間愈短。例如O(n)比O(n2)更有效率。

72 【舉例】假設有一個問題，分別利用七種不同演算法來解決， 請問下表中，那一種方法最佳，那一種方法最差？
【解答】假設每一種演算法都必須輸入資料量(n=10)時， 則它們的時間複雜度大小順序為： O(log2 n) < O(n) < O(n log2 n) < O(n2 )< O(n3 )< O(2n )< O(n! )

73 延伸學習<觀念> 評估演算法的三種方法： 一、O(n)( Big-O of n)：最常被使用，用來表示理論「上限」
二、Ω(n) (Big-Omega of n)：用來表示理論「下限」 三、Θ(n)(Big-Theta of n)：表示理論「上限與下限」

74 延伸學習<觀念> 一、O(n)( Big-O of n)：最常被使用，用來表示理論「上限」 【假設】
g(n)：Big-O取執行次數中最高次方或最大指數部份的項目。 若且唯若f(n)=O(g(n))，則存在一正整數c及n0，對所有的n值而言，當nn0時，則f(n)c*g(n)均成立。

75 延伸學習<證明> 【題目】證明f(n)＝3n+2，可以用Ο(n)來表示。 【解答】 假設f(n)c*g(n)關係式成立
∴3*n＋2≦c*n (因為f(n)=O(g(n)) ∴(c-3)*n≧2 當c＝4時，則n≧2，所以n0＝2 (因為nn0) 所以只要c≧4，且n0 ≧2時，則3*n＋2≦4*n ∴f(n)＝ 3n＋2，就可以用Ο(n)來表示。

76 延伸學習<證明> 【題目】證明f(n)＝10n2+5n+1 , 可用O(n2)表示。 【解答】
假設f(n)c*g(n)關係式成立 ∴10 n2+5n+1 ≦ c*n2 (因為f(n)=O(g(n)) ∴(c-10)n2≧5n+1 當c=11，則上式為n2≧5n+1 並且當n≧6時，則 n2≧5n+1， 所以n0=6(因為nn0) 所以只要c≧11，n0≧6則10 n2+5n+1≦11n2 ∴f(n)= 10 n2+5n+1可以用O(n2)表示

77 延伸學習<觀念及證明> 二、Ω(n) (Big-Omega of n)：用來表示理論「下限」
若且唯若f(n)=(g(n))，則存在一正整數c及n0，對所有的n值而言，當nn0時，則f(n)c*g(n)均成立。 【題目】證明f(n)＝3n+2，可以用Ω(n)來表示。 【解答】 假設f(n)≧c*g(n)關係式成立 　∴3*n＋2≧c*n 　∴(3-c)*n≧-2 　當c＝2時，並且n>1，上式即可成立 　∴找到c＝2， n0＝1(因為nn0)時，則3n+2 ≧ 2n2 ∴f(n)= 3n+2可以用Ω(n)表示

78 延伸學習<證明> 【題目】證明f(n)＝200 n2+4n+5, 可用Ω(n2)表示。 【解答】
假設f(n)≧c*g(n)關係式成立 ∴200 n2+4n+5 ≧ c*n2 ∴(200-c)n2 +4n+5 ≧0 ∴ c=200，n>1時上式成立， 找的到c=200，n0=1 (因為nn0)時，則200 n2+4n+5 ≧ 200n2 ∴f(n)= 200 n2+4n+5可以用Ω(n2)表示

79 延伸學習<觀念> 三、Θ(n)(Big-Theta of n)：表示理論上限與下限。
是一種比Big-O與Ω更精確時間複雜度的漸近表示法。 若且唯若f(n)=(g(n))，則存在一正整數c1、c2及n0，對所有的n值而言，當nn0時，則c1*g(n )  f(n)  c2*g(n)均成立。

80 延伸學習<證明> 【題目1】證明f(n)＝3n+1，可以用Θ(n)來表示。 【解答】
假設c1*g(n )  f(n)  c2*g(n) 關係式成立 ∴c1*n≦3*n＋1 ∴3*n＋1≦c2*n 當c1＝3，c2＝4時， n>2，上式即可成立 ∴找到c1＝3，c2＝4 ，n0＝2 (因為nn0)時，則3n≦3n+1≦4n 所以f(n)＝3n＋1可以用Θ(n)來表示

81 延伸學習<證明> 【題目2】證明f(n)＝10n2+4n+6，可以用Θ(n2)來表示。 【解答】
假設c1*g(n )  f(n)  c2*g(n) 關係式成立 ∴c1n2≦10n2+4n+6 ∴10n2+4n+6 ≦c2n2 當c1＝10，c2＝11時，n>10 ，上式即可成立 ∴找到c1＝10，c2＝11 ， n0＝10 (因為nn0)時， 則10n2≦10n2+4n+6 ≦11n2 所以f(n)＝10n2+4n+6可以用Θ(n 2)來表示

82 1-6.2 空間複雜度(Space Complexity)
【定義】 一個程式P的空間複雜度(Space Complexity)包含固定的空間需求與 變動的空間需求兩個部分。

83 一、固定的空間需求 【定義】 包含了程式在編譯時期所產生的空間需求。例如程式本身的指令、常數、靜態變數及結構等。

84 二、變動空間需求 【定義】 是指從呼叫該副程式開始到完成之過程，所有佔用的「記憶體空間」。例如：參數、變數宣告，回傳值以及傳回位址時，都會佔用記憶體空間。 說明：保存A函數當時執行時之狀態 包括參數值區域變數值返回位址

85 一、固定的空間需求 【定義】 包含了程式在編譯時期所產生的空間需求。例如程式本身的指令、常數、靜態變數及結構等。