1、1/3/20231細說資料結構本章學習目標本章學習目標 1.1.讓讀者了解讓讀者了解、及及之間的關係，以及之間的關係，以及的的。2.2.讓讀者了解讓讀者了解與與的的差異差異。1/3/20232本章內容本章內容 1-1 1-1 認識資料與資訊的關係認識資料與資訊的關係1-2 1-2 何謂資料結構？何謂資料結構？1-3 1-3 何謂演算法何謂演算法?1-4 1-4 程式設計概念程式設計概念1-5 1-5 結構化程式設計結構化程式設計1-6 1-6 演算法的效率評估演算法的效率評估 1/3/202331-1 認識資料與資訊的關係認識資料與資訊的關係1.資料資料(Data)：是指：是指未經過處理未經過
2、處理的的原始記錄原始記錄，例如學生考試的，例如學生考試的原始成績原始成績。2.資訊資訊(Information)：就是：就是有經過處理有經過處理的的結果結果，例如全班同學，例如全班同學成績之排名成績之排名 及及分佈圖分佈圖。*資料處理資料處理(DP)：是將：是將資料資料轉換成轉換成資訊資訊的一連串的處理過程。的一連串的處理過程。1/3/202341.資料資料(Data)(1)(1)是是客觀客觀存在的、存在的、具體的具體的、事實的事實的記錄。記錄。(2)(2)簡單來說，日常生活中所記錄的簡單來說，日常生活中所記錄的事實資料事實資料(姓名、生日、電話及地址姓名、生日、電話及地址)或學生在期中考的或
3、學生在期中考的各科原始成績各科原始成績，這些都是，這些都是未經過資料處理未經過資料處理的資料。的資料。如表如表1-11-1所示。所示。1/3/202352.資訊資訊(Information)(1)(1)經過經過資料處理之後資料處理之後的的結果結果即為即為資訊資訊。其資料與資訊的特性比較。其資料與資訊的特性比較。如表如表1-21-2所示。所示。1/3/20236(2)(2)處理程序處理程序(例如：成績處理系統例如：成績處理系統)會將會將原始資料原始資料以加整理、計算及分析以加整理、計算及分析 之後，變成之後，變成有用的資訊有用的資訊(含含總成績、平均及排名次總成績、平均及排名次)。如表。如表1-
4、3 1-3 所示。所示。1/3/20237(3)(3)是是決策者決策者在思考某一個問題時所在思考某一個問題時所需用到的資料，需用到的資料，它是它是主觀認定主觀認定的。例的。例 如：如：班導師班導師(決策者決策者)在學生考完期中考之後，想依學生在學生考完期中考之後，想依學生考試成績來獎考試成績來獎 勵勵，因此，班導師必須要有一份，因此，班導師必須要有一份全班排名的成績單全班排名的成績單(資訊資訊)，以做為獎，以做為獎 勵的依據。勵的依據。1/3/202381-2 何謂資料結構？何謂資料結構？(Data Structures)主要是探討如何將資料主要是探討如何將資料更有組織更有組織地存放地存放到到
5、電腦記憶體電腦記憶體中，以中，以提昇提昇程式之程式之執行效率執行效率的一門學問。的一門學問。因此，有因此，有（Data structure）及）及（Algorithm）將可以大大的）將可以大大的提昇程式的執行效率提昇程式的執行效率。1/3/20239在電腦科學在電腦科學(Computer Science)的領域中，我們如何透過電腦來取得的領域中，我們如何透過電腦來取得即時即時的的、有用的資訊有用的資訊，那就必須先要撰寫，那就必須先要撰寫有效率有效率及及正確正確的的去運作，而去運作，而就是由就是由和和所構成的。所構成的。其公式如下：其公式如下：其中：其中：是指：是指資料在記憶體中的儲存方式資料在
6、記憶體中的儲存方式，:則是則是如何將資料作有效率的處理過程如何將資料作有效率的處理過程。因此，當我們在撰寫程式時，只有因此，當我們在撰寫程式時，只有，才能夠設計，才能夠設計出出，進而轉換成為，進而轉換成為。1/3/202310 基本上，資料結構包含有基本上，資料結構包含有遞迴遞迴(Recursive)、陣列陣列(Array)、堆疊堆疊(Stack)、佇列佇列(Queue)、串列串列(List)、樹狀樹狀(Tree)、圖形圖形(Graph)、排序排序(Sort)及及搜尋搜尋(Search)等單元，雖然這幾種資料結構單元乍看之下，好像等單元，雖然這幾種資料結構單元乍看之下，好像非常理論與抽象，但是
7、在我們日常生活中，卻經常可以看到非常理論與抽象，但是在我們日常生活中，卻經常可以看到。1/3/202311【舉例舉例】遞迴遞迴(Recursive)：老鼠走迷宮的問題老鼠走迷宮的問題就是屬於遞迴結構。就是屬於遞迴結構。陣列陣列(Array)：教室座位排列方式教室座位排列方式就是屬於陣列結構。就是屬於陣列結構。堆疊堆疊(Stack)：碗盤的疊法碗盤的疊法、小朋友排積木小朋友排積木、書本裝箱書本裝箱或或座電梯座電梯等都等都 具有具有後進先出後進先出的特性就是屬於堆疊結構。的特性就是屬於堆疊結構。佇列佇列(Queue)：排隊買票看球賽排隊買票看球賽，先到先買先到先買的方式就是所謂的的方式就是所謂的
8、佇列結構佇列結構1/3/202312【舉例舉例】串列串列(List)：高鐵火車的：高鐵火車的車箱串接方式車箱串接方式就是屬於串列結構。就是屬於串列結構。樹狀樹狀(Tree)：如果球賽的：如果球賽的賽程方式是採用淘汰制賽程方式是採用淘汰制，就是一種樹狀結構。，就是一種樹狀結構。圖形圖形(Graph)：當看完球賽要回家的：當看完球賽要回家的行駛路線圖行駛路線圖，則可視為所謂的圖形，則可視為所謂的圖形 結構。結構。排序排序(Sort)：球賽：球賽成績的結果之排名方式成績的結果之排名方式就是屬於排序結構。就是屬於排序結構。搜尋搜尋(Search)：球賽比賽之前：球賽比賽之前找尋某一隊的賽程找尋某一隊的
9、賽程就是屬於搜尋結構。就是屬於搜尋結構。1/3/202313【老師上課動態展示老師上課動態展示】檔案在附書光碟中。檔案在附書光碟中。1/3/202314【實例實例】撰寫一個程式來計算撰寫一個程式來計算5 5位同學的資料結構平均成績，並且比較位同學的資料結構平均成績，並且比較沒沒有有使用使用資料結構資料結構與與演算法演算法的差異。的差異。1/3/202315第一種方法沒有使用資料結構與演算法，而是使用一般變數的宣告方式第一種方法沒有使用資料結構與演算法，而是使用一般變數的宣告方式來個別存放成績資料。雖然也可以順利的計算出所需要的結果，但是，來個別存放成績資料。雖然也可以順利的計算出所需要的結果，
10、但是，因為，當我們要計算的，因為，當我們要計算的，程式將會，程式將會。例如：全班學生人數為例如：全班學生人數為50人時，則行號人時，則行號03的程式碼就會變數非常的長，的程式碼就會變數非常的長，1/3/202316第二種方法是使用第二種方法是使用來存放來存放5位同學的成績資料，然後位同學的成績資料，然後再使用再使用來計算來計算5位同學的成績，最後再列印出結果。位同學的成績，最後再列印出結果。比較分析：比較分析：第二種方法的程式第二種方法的程式，也就是說，當我們要計算的學生，也就是說，當我們要計算的學生時，只要時，只要及及即可。即可。1/3/2023171-3 何謂演算法何謂演算法?演算法在演算
11、法在中定義為：中定義為：。我們可以把。我們可以把定義成：定義成：。它可以是利用它可以是利用、或、或或或的方式，來表示解決問題的的方式，來表示解決問題的 步驟。步驟。1/3/202318一、撰寫演算法應遵守五點原則：一、撰寫演算法應遵守五點原則：不一定不一定要有輸入。要有輸入。可能沒有可能沒有，也可能是，也可能是多個資料輸入多個資料輸入。例如例如(1)：取得系統目前的時間，不須要輸入取得系統目前的時間，不須要輸入，只要寫一行，只要寫一行now()函數，函數，就可以輸出系統時間。就可以輸出系統時間。例如例如(2)：求某數為奇偶數時求某數為奇偶數時，則必須，則必須先要有一個整數輸入先要有一個整數輸入
12、，才能進行，才能進行 判斷。判斷。1/3/202319一、撰寫演算法應遵守五點原則：一、撰寫演算法應遵守五點原則：(續續)：至少一個輸出至少一個輸出。例如：在電腦中，處理資料的基本過程有三個步驟：例如：在電腦中，處理資料的基本過程有三個步驟：輸入輸入 處理處理 輸出輸出 (原始資料原始資料)(程式程式)(有用的資訊有用的資訊)所以，使用電腦來為我們處理資料時，有可能是系統自動接收到一個訊號，所以，使用電腦來為我們處理資料時，有可能是系統自動接收到一個訊號，來當作輸入資料，但是來當作輸入資料，但是系統至少會輸出一項系統至少會輸出一項讓使用者參考的讓使用者參考的有用資訊有用資訊。1/3/20232
13、0一、撰寫演算法應遵守五點原則：一、撰寫演算法應遵守五點原則：(續續)：每一行每一行指令指令都都必須明確，不可模稜兩可。必須明確，不可模稜兩可。例如：判斷某一數值是否為偶數。例如：判斷某一數值是否為偶數。首先我們試著用下列文字來加以描述：首先我們試著用下列文字來加以描述：(1)(1)輸入一個正整數。輸入一個正整數。(2)(2)作餘除運算是否為作餘除運算是否為0 0。(3)(3)為為0 0即為偶數。即為偶數。以上描述看來似乎正確，但是從演算法觀點來看，其中的第以上描述看來似乎正確，但是從演算法觀點來看，其中的第(2)(2)點並點並不符合明確性，因它並未說明不符合明確性，因它並未說明餘除運算餘除運
14、算是如何運算，容易造是如何運算，容易造成混淆與不解。我們應該改寫為：成混淆與不解。我們應該改寫為：(1)(1)輸入一個正整數輸入一個正整數N N。(2)(2)如果如果N N 除以除以2 2，其餘數為，其餘數為0 0。(3)(3)則其則其N N為偶數。為偶數。不具明確性具明確性1/3/202321一、撰寫演算法應遵守五點原則：一、撰寫演算法應遵守五點原則：(續續)例如：例如：用功的學生用功的學生才能領獎學金就才能領獎學金就不具有明確性不具有明確性，因為每一個人對用功，因為每一個人對用功的定義可能不盡相同，而如果改為的定義可能不盡相同，而如果改為成績成績9090以上以上的學生才能領的學生才能領獎學
15、金就是獎學金就是具有明確性具有明確性，因為，因為9090分分是一個是一個比較客觀的定義比較客觀的定義。1/3/202322一、撰寫演算法應遵守五點原則：一、撰寫演算法應遵守五點原則：(續續)：演算法：演算法不能有無窮迴路不能有無窮迴路，必須能終止執行必須能終止執行。由於由於演算法並非是真正可以執行的程式演算法並非是真正可以執行的程式，而是設計者所推演出解決問題，而是設計者所推演出解決問題的步驟，因此，必須在的步驟，因此，必須在有限的步驟有限的步驟內要完成內要完成解決問題的程序解決問題的程序。但是，真。但是，真正的程式是可以有無窮迴路的動作。正的程式是可以有無窮迴路的動作。例如：例如：Windo
16、ws Windows 作業系統除非系統關機或當機，否則它會永遠執行一個作業系統除非系統關機或當機，否則它會永遠執行一個等待迴圈，來等待使用者從鍵盤輸入或其他的輸入設備。等待迴圈，來等待使用者從鍵盤輸入或其他的輸入設備。1/3/202323一、撰寫演算法應遵守五點原則：一、撰寫演算法應遵守五點原則：(續續)：既然既然演算法演算法是是解決問題的方法解決問題的方法，因此，因此，正確性是正確性是最基本的要求最基本的要求。例如：以下判斷某數為奇偶數的演算法，雖然符合明確性，但是例如：以下判斷某數為奇偶數的演算法，雖然符合明確性，但是 不正確不正確，因為，因為N 除以除以2，其餘數為，其餘數為0，則，則N
17、應該為偶數，應該為偶數，而非奇數。而非奇數。輸入一個正整數輸入一個正整數N。如果如果N 除以除以2，其餘數為，其餘數為0。則其則其N為為奇數奇數。應該改為應該改為偶數偶數 1/3/202324【日常生活中的例子日常生活中的例子】一組可用來解決特定問題的有限指令或步驟，依循這些指令或步驟，可以進一組可用來解決特定問題的有限指令或步驟，依循這些指令或步驟，可以進行解題。行解題。食譜食譜 -做蛋糕做蛋糕圖片來源：163.23.171.96/cornliu/cornppt/第六章.ppt 1/3/202325好吃的蛋糕怎麼來好吃的蛋糕怎麼來?圖片來源：163.23.171.96/cornliu/cor
18、nppt/第六章.ppt 1/3/202326二、描述演算法有三種方法：二、描述演算法有三種方法：(一一)文字敘述文字敘述演算法可用文字加以描述，但是採用口語化的文字敘述來加以描述，其演算法可用文字加以描述，但是採用口語化的文字敘述來加以描述，其缺缺點點在於在於冗長且較不精確冗長且較不精確，在撰寫、閱讀、會意時，在撰寫、閱讀、會意時可能會有誤差可能會有誤差，因此，因此一般一般較不常用。較不常用。例如：請利用文字敘述使用者登入帳號與密碼時，系統檢查的過程。例如：請利用文字敘述使用者登入帳號與密碼時，系統檢查的過程。步驟一：輸入使用者帳號與密碼步驟一：輸入使用者帳號與密碼步驟二：判斷帳號與密碼是否
19、正確步驟二：判斷帳號與密碼是否正確步驟三：如果正確時，則可以登入系統步驟三：如果正確時，則可以登入系統 否則，就無法登入！否則，就無法登入！1/3/202327(二二)流程圖（流程圖（FlowchartFlowchart）是指利用是指利用來表達欲來表達欲。當我們想利。當我們想利用電腦程式語言來處理問題時，先要了解問題並想出許多方案來解決用電腦程式語言來處理問題時，先要了解問題並想出許多方案來解決問題，並且分析那些資料是要問題，並且分析那些資料是要，經過，經過之後，要之後，要那些結果。那些結果。1/3/2023281/3/2023291/3/202330【舉例舉例】請繪出使用者登入帳號與密碼時，
20、系統檢查的流程圖。請繪出使用者登入帳號與密碼時，系統檢查的流程圖。1/3/202331(三三)虛擬碼（虛擬碼（Pseudo Code）虛擬碼虛擬碼兼具兼具文字描述文字描述及及流程圖流程圖的優點，其方式是用文字摻雜程式語的優點，其方式是用文字摻雜程式語言，來描述解題步驟與方法。言，來描述解題步驟與方法。例如例如1：請利用：請利用虛擬碼（虛擬碼（Pseudo Code）敘述使用者登入帳號與密敘述使用者登入帳號與密碼時，系統檢查的過程。碼時，系統檢查的過程。(1)Input:UserName,Password(2)IF(UserName And Password)ALL True Output:Yo
21、u Can Pass!else Output:You Can not Pass!1/3/202332例如：例如：1+2+3+10虛擬碼可以描述如下：虛擬碼可以描述如下：(1)設設Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若若Count 10 則至步驟則至步驟(5)，否則回步驟，否則回步驟(2)(5)印出印出Total1/3/2023331-4 程式設計概念程式設計概念我們要開始程式設計時，一定要進行下面五個步驟：我們要開始程式設計時，一定要進行下面五個步驟：1/3/2023341/3/2023351/3/202336實例實
22、例計算國文與英文的平均成績，並依照平均成績來求顯示及格與不及計算國文與英文的平均成績，並依照平均成績來求顯示及格與不及格。格。1.1.分析及定義問題。分析及定義問題。兩個等級分別如下：兩個等級分別如下：(1)(1)及格：及格：60(60(含含)以上。以上。(2)(2)不及格：不及格：6060以下。以下。2.2.畫出整合問題的流程圖或撰寫問題的演算法。畫出整合問題的流程圖或撰寫問題的演算法。1/3/2023373.3.撰寫及建立程式模組。撰寫及建立程式模組。1/3/2023384.4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止。對每一個程式模組進行測試及除錯，直到沒有錯誤為止。當使用者輸入
23、國文為當使用者輸入國文為60分，英文為分，英文為61分時，是否可以計算出平均成分時，是否可以計算出平均成績為績為60.5，如果沒有則必須要進行除錯，亦即要將，如果沒有則必須要進行除錯，亦即要將Average的資料型態的資料型態改為改為float(浮點數浮點數)。1/3/202339【重要觀念重要觀念】系統發展的生命週期與程式設計之步驟比較系統發展的生命週期與程式設計之步驟比較 1/3/2023401-4.1 演算法與程式的差異？演算法與程式的差異？1.1.是以是以為主，亦即任何人都可以閱讀的程式碼，為主，亦即任何人都可以閱讀的程式碼，因此，必須特別強調因此，必須特別強調。2.2.則是以則是以為
24、主，它強調程式的執行結果為主，它強調程式的執行結果、可、可及及。1/3/2023411-4.2為什麼要撰寫程式為什麼要撰寫程式?我們為什麼要花那麼多時間來撰寫程式呢？其主要的目的：它可以我們為什麼要花那麼多時間來撰寫程式呢？其主要的目的：它可以快快速解決複雜的問題速解決複雜的問題。甲同學說：請電腦幫我計算甲同學說：請電腦幫我計算1 1加到加到1010的總合。的總合。或許你會認為這簡單的問題，你我都會算，何必寫程式呢？或許你會認為這簡單的問題，你我都會算，何必寫程式呢？但是，如果甲同學又說：請電腦幫我計算但是，如果甲同學又說：請電腦幫我計算1 1加到加到5000050000時，我想我們就時，我想
25、我們就無法馬上計算出結果。由上面的例子，無法馬上計算出結果。由上面的例子，我們可以非常清楚的知道，程式我們可以非常清楚的知道，程式語言幫忙人類解決複雜的問題語言幫忙人類解決複雜的問題。1/3/2023421-4.3 一個好程式需要滿足條件一個好程式需要滿足條件一、正確性一、正確性(Correctness)二、效率性二、效率性(Performance)三、可維護性三、可維護性(Maintainable)1/3/202343一、正確性一、正確性(Correctness)既然演算法是既然演算法是解決問題的方法解決問題的方法，因此，將演算法實作為程式之後，也必，因此，將演算法實作為程式之後，也必須要能
26、夠解決某一問題，所以，須要能夠解決某一問題，所以，正確性正確性是一個是一個好程式最基本的要求好程式最基本的要求。例如：設計一個判斷奇偶數的程式例如：設計一個判斷奇偶數的程式 說明：上面的程式處理過程中，由於程式不正確，所以產生錯誤的結果。說明：上面的程式處理過程中，由於程式不正確，所以產生錯誤的結果。1/3/202344二、效率性二、效率性(Performance)一般一般評估執行時間的方法評估執行時間的方法就是看原始程式碼中所有就是看原始程式碼中所有敘述所被執行的總次敘述所被執行的總次數數來計算。亦即所謂的來計算。亦即所謂的頻率次數頻率次數(Frequency Count)，當，當頻率頻率次
27、次數愈高數愈高時，代表所需的時，代表所需的執行時間愈長執行時間愈長。例如：計算下列程式中變數例如：計算下列程式中變數Count被執行的次數為何？被執行的次數為何？NoImage1/3/202345三、可維護性三、可維護性(Maintainable)一個好的程式，不只需要有效率地被正確地執行之外，也必須要考慮程式的一個好的程式，不只需要有效率地被正確地執行之外，也必須要考慮程式的可讀性可讀性、及、及未來修改未來修改和和擴充性擴充性，這屬於程式設計，這屬於程式設計方法和風格方法和風格的問題，例如：的問題，例如：使用使用模組化模組化來設計程式和加上完整程式來設計程式和加上完整程式註解註解的說明。的說
28、明。1/3/2023461-5 結構化程式設計結構化程式設計何謂何謂結構化程式設計結構化程式設計呢？它是利用呢？它是利用由上而下由上而下的技巧，將程式的技巧，將程式分解分解成多個具有成多個具有獨立功能獨立功能的的模組模組。如圖。如圖1-51-5所示。所示。圖圖1-5 1-5 結構化程式設計的示意圖結構化程式設計的示意圖1/3/202347結構化程式設計由結構化程式設計由Dijkstra(1969)提出：提出：1.消除程式因消除程式因goto而造成如麵條式的而造成如麵條式的混亂狀態混亂狀態。2.強調任何程式邏輯均可由強調任何程式邏輯均可由三種結構三種結構組成。如圖組成。如圖1-6所示。所示。(1
29、)循序循序(Sequence)：簡單命令式的指令簡單命令式的指令如如 COMPUTE,READ,WRITE 與代數指令與代數指令如如X=Y+Z。(2)選擇選擇(Condition)：需：需做決策做決策時，用時，用 IF-THEN-ELSE 指令指令與與 CASE 指令指令。(3)重複重複(Repetition)：當：當需反覆需反覆時，用時，用 DO-WHILE 與與 DO-UNTIL 指令指令。1/3/2023481/3/2023491-5.1 循序結構循序結構所謂所謂循序結構循序結構，是指程式，是指程式由上而下，依序逐一執行由上而下，依序逐一執行。亦即。亦即程式碼被程式碼被執行的順序為由上而
30、下，一個敘述接著一個敘述依序執行執行的順序為由上而下，一個敘述接著一個敘述依序執行。此種結。此種結構是最基本的結構。如圖構是最基本的結構。如圖1-71-7所示：所示：1/3/2023501-5.2 選擇結構選擇結構如果只希望在如果只希望在某種條件成立某種條件成立時時才執行才執行某些敘述，而某種條件某些敘述，而某種條件不成立不成立才才執行另一種敘述執行另一種敘述，來，來過濾一些條件過濾一些條件。那我們就必須使用選擇結構。那我們就必須使用選擇結構的方式了。如圖的方式了。如圖1-81-8所示。所示。1/3/202351此種結構是此種結構是最常被使用最常被使用的方式，因為大部份的的方式，因為大部份的選
31、擇結構選擇結構的情況的情況可能是兩種可能是兩種。例如：判斷例如：判斷及格及格與與不及格不及格、判斷、判斷奇數奇數與與偶數偶數、判斷、判斷男生男生與與女生女生 等情況，都可以利用此種結構來完成。等情況，都可以利用此種結構來完成。1/3/2023521.語法：語法：其中其中(條件式條件式)是一是一關係運算式關係運算式 或或 邏輯運算式邏輯運算式2.說明：如果說明：如果條件式成立條件式成立(真真)，就，就執行執行 Then後面後面的的敘述區塊敘述區塊1 ，否則就執行敘述區塊，否則就執行敘述區塊2。3.注意：當敘述區塊內的注意：當敘述區塊內的敘述只有一行敘述只有一行時，則可以時，則可以省略左右大括號省
32、略左右大括號。4.使用時機：當條件只有使用時機：當條件只有二種情況二種情況時最佳方法。時最佳方法。1/3/2023535.5.流程圖：如圖流程圖：如圖1-91-9所示：所示：1/3/2023541-5.3 重複結構重複結構 在處理在處理一再重複的相同動作一再重複的相同動作，這對，這對電腦而言電腦而言，是一件，是一件非常非常Easy的的事事，但對我們，但對我們人類人類而言卻是一而言卻是一件苦差事件苦差事，因此驅使電腦做這樣的事情，因此驅使電腦做這樣的事情的方式，就是迴圈的方式，就是迴圈(Loop)，亦即，亦即讓某一段程式反覆執行多次的敘述讓某一段程式反覆執行多次的敘述，我們稱此結構為我們稱此結構
33、為迴圈結構迴圈結構。1/3/202355如果我們想要撰寫一段程式，來輸出如果我們想要撰寫一段程式，來輸出1,2,100時，怎麼辦？目前最少時，怎麼辦？目前最少有兩種方法可以使用。如圖有兩種方法可以使用。如圖1-10所示：所示：1/3/2023561-6 演算法的效率評估演算法的效率評估演算法的效率評估演算法的效率評估指的是用來計算指的是用來計算某些演算法某些演算法所撰寫的所撰寫的程式程式在在經過編譯經過編譯之之後後實際執行所需要的時間實際執行所需要的時間。但是，實務上有可能因為程式。但是，實務上有可能因為程式編譯的過程編譯的過程或是或是電腦設備的差異電腦設備的差異使得效率分析會因電腦的使得效率
34、分析會因電腦的軟硬體不同而有不同的結果軟硬體不同而有不同的結果，因，因此，一般而言，效率的評估方式可分為兩大類：此，一般而言，效率的評估方式可分為兩大類：一、時間複雜度（一、時間複雜度（Time Complexity）二、空間複雜度（二、空間複雜度（Space Complexity）1/3/202357一、時間複雜度（一、時間複雜度（Time Complexity）是指從是指從呼叫該呼叫該開始到完成之過程開始到完成之過程，所有花費的所有花費的。基本上，基本上，影響程式影響程式的因素的因素，有種兩因素：，有種兩因素：1.演算法效率的好壞演算法效率的好壞2.機器的機器的CPU執行速度執行速度所以，
35、所以，執行時間執行時間=執行次數執行次數*每次執行所需的時間每次執行所需的時間。1/3/202358由於由於每一行程式每一行程式所所需的時間需的時間必須考慮到必須考慮到機器本身的機器本身的CPUCPU執行速度執行速度及及編編譯器譯器的功能，所以，的功能，所以，在評估上比較不客觀在評估上比較不客觀。因此，通常只考慮。因此，通常只考慮，所以，在，所以，在相同功能的條件之下相同功能的條件之下，往往是用來，往往是用來。也就是說，我們必須先計算出程式中。也就是說，我們必須先計算出程式中每一敘每一敘述的執行次數述的執行次數，再一一的，再一一的加總起來加總起來，然後再，然後再求出其求出其Big-OBig-O
36、。例如：計算下列程式中變數例如：計算下列程式中變數Count被執行的次數為何？被執行的次數為何？1/3/202359二、空間複雜度（二、空間複雜度（Space Complexity）是指從是指從呼叫該副程式呼叫該副程式開始到完成之過程，所有開始到完成之過程，所有佔用的記憶體空間佔用的記憶體空間。例如：參數、變數宣告，回傳值以及傳回位址時，都會佔用記憶體空間。例如：參數、變數宣告，回傳值以及傳回位址時，都會佔用記憶體空間。1/3/2023601/3/202361時間複雜度時間複雜度與與空間複雜度空間複雜度之分析之分析 基本上，基本上，的分析比的分析比空間複雜度空間複雜度來得來得，因為，因為當資料
37、量龐當資料量龐大大時，時，時間複雜度會有時間複雜度會有，但是，但是，空間複雜度則差異空間複雜度則差異，再加上目前的記憶體相當便宜，因此，目前在資料結構所探討演算法再加上目前的記憶體相當便宜，因此，目前在資料結構所探討演算法之效率評估，都著重在之效率評估，都著重在。1/3/2023621-6.1 時間複雜度時間複雜度(Time complexity)是指是指計算計算執行執行程式所花費的時間程式所花費的時間。一般而言，我們可以將一個。一般而言，我們可以將一個程式程式P P的的時間複雜度時間複雜度表示成表示成T(P)T(P)的形式。而的形式。而T(P)T(P)記錄記錄了程式了程式執行次數執行次數n
38、n的的成長速率成長速率。1/3/202363【舉例舉例1】假設有一陣列假設有一陣列a，其陣列的大小為，其陣列的大小為n，如果要將陣列，如果要將陣列a的的元素相加元素相加，請，請問程式的執行次數為何？問程式的執行次數為何？【解析解析】行號行號04會執行會執行n+1次，而前次，而前n次會執行迴圈主體，但是在第次會執行迴圈主體，但是在第n+1次時次時 沒有符合迴圈的條件，故離開迴圈。沒有符合迴圈的條件，故離開迴圈。1/3/202364【舉例舉例2】假設兩矩陣假設兩矩陣a,b相加相加，並且矩陣大小皆為，並且矩陣大小皆為n*n，請計算出下列程式，請計算出下列程式的執行次數。的執行次數。【解析解析】行號行
39、號04外層迴圈外層迴圈(for)的計數器的計數器i從從0n-1，共會執行，共會執行n+1次，而次，而行號行號05內層迴圈內層迴圈(for)的計數器的計數器j從從0n-1，也會執行，也會執行n+1次。因此，當外次。因此，當外層迴圈執行層迴圈執行1次時，則內層迴圈要執行一回合，也就是次時，則內層迴圈要執行一回合，也就是j從從0n-1(共有共有n次次)arababaabababaabnnbbanabccbccccccrccnalog1)7()6(log1log)5(logloglog)4(logloglog)3(loglog)(log)2(logln)1(logloglog21/3/202365【舉
40、例舉例3】假設兩矩陣假設兩矩陣a,b相乘相乘，並且矩陣大小皆為，並且矩陣大小皆為n*n，相加請計算出下列，相加請計算出下列程式的執行次數。程式的執行次數。1/3/202366在經過上面例子，來算出程式敘述的執行次數後，在經過上面例子，來算出程式敘述的執行次數後，我們雖然可以利用我們雖然可以利用理論上下限理論上下限(n)比比理論上限理論上限O(n)與與理論下限理論下限(n)都來得準確，但都來得準確，但是在通常利用是在通常利用來表示此演算法的來表示此演算法的，亦，亦稱為該程式的稱為該程式的 1/3/202367一、一、O(n)(Big-O of n)的定義：的定義：最常被使用，用來表示理論上限最常
41、被使用，用來表示理論上限O(n)可視為某演算法在電腦中所需可視為某演算法在電腦中所需執行時間執行時間，亦即某演算法的，亦即某演算法的執行時間執行時間T(n)的時間複雜度的時間複雜度(time complexity)為為O(n)(讀成讀成Big-O of n)。Big-O取執行次數取執行次數中中最高次方最高次方或或最大指數部份最大指數部份的項目即可。的項目即可。如：如：陣列元素相加為陣列元素相加為2n+3=O(n)矩陣相加為矩陣相加為2n2+2n+2=O(n2)矩陣相乘為矩陣相乘為2n3+4n2+2n+2=O(n3)1/3/202368因此，透過因此，透過時間複雜度分析時間複雜度分析之觀念，我們
42、就可以判斷某些程式的之觀念，我們就可以判斷某些程式的執行執行效率是否良好。效率是否良好。【假設假設】f(n)：統計的：統計的執行次數執行次數。g(n)：Big-O取取執行次數中最高次方執行次數中最高次方或或最大指數部份最大指數部份的項目。的項目。f(n)=O(g(n)，若且唯若，存在一正整數，若且唯若，存在一正整數c及及n0，對所有的，對所有的n，n n0時，時，則則f(n)c*g(n)。1/3/202369【舉例舉例】矩陣相加矩陣相加的執行次數為的執行次數為2n2+2n+2 1.f(n)就會等於就會等於2n2+2n+2 亦即：亦即：f(n)=2n2+2n+2 2.g(n)則取則取f(n)中的
43、最高次方中的最高次方 亦即：亦即：g(n)=n2 f(n)=O(g(n)1/3/2023701/3/2023711/3/202372二、二、(n)(Omega of n)定義：定義：用來表示理論下限用來表示理論下限f(n)=(g(n)，若且唯若，存在正整數，若且唯若，存在正整數c及及n0，對所有的，對所有的n，n n0時，時，則則f(n)c*g(n)。1/3/2023731/3/202374三、三、(n)(Theta of n)定義：定義：表示理論上限與下限均為此函數表示理論上限與下限均為此函數是一種比是一種比Big-O與與更精確更精確時間複雜度的時間複雜度的漸近表示法漸近表示法。f(n)=(
44、g(n)，若且唯若，存在正整數，若且唯若，存在正整數c1、c2及及n0，對所有的，對所有的n，n n0時，則時，則c1*g(n)f(n)c2*g(n)。1/3/2023751/3/202376四、時間複雜度的等級四、時間複雜度的等級若若n n代表資料的數量，時間複雜度可分為下列不同的等級：代表資料的數量，時間複雜度可分為下列不同的等級：1/3/2023771/3/2023781-6.2 空間複雜度空間複雜度(Space Complexity)一個程式一個程式P的空間複雜度的空間複雜度(Space Complexity)包含包含固定的空間需求固定的空間需求與與變變動的空間需求動的空間需求兩個部分
45、。兩個部分。一、固定的空間需求一、固定的空間需求 包含了程式在編譯時期包含了程式在編譯時期(Compile Time)所產生的空間需求。例如所產生的空間需求。例如程式本身的程式本身的指令空間、常數、靜態變數及結構指令空間、常數、靜態變數及結構等。等。二、變動空間需求二、變動空間需求 包含了包含了動態記憶體動態記憶體要求要求(Dynamic Memory Allocation)所配置的空所配置的空間，以及間，以及遞迴函數遞迴函數執行時所需要用來儲存活動紀錄執行時所需要用來儲存活動紀錄(Activation Record)的執行時的執行時堆疊空間堆疊空間(Run Time Stack)。1/3/2
46、02379通常我們會利用通常我們會利用S(P)來表示一個來表示一個程式程式P所需的所需的空間需求空間需求，公式：公式：S(P)=c+SP(I)其中：其中：c代表這個程式的代表這個程式的固定空間需求固定空間需求SP(I)則表示則表示程式程式P針對特定的輸入針對特定的輸入資料集合資料集合I(Instance)所需的所需的變動空間需求變動空間需求。1/3/202380【實例實例】試試”著計算出三個整數之平均著計算出三個整數之平均”的空間複雜度為何？的空間複雜度為何？【解答解答】在上面的例子中，在上面的例子中，Add函數有函數有3個參數個參數及及1個傳回值個傳回值，因此，固定的空間，因此，固定的空間需求為需求為(3+1)*2bytes=8bytes，而，而Add函數並沒有使用到動態配置記憶體函數並沒有使用到動態配置記憶體，所以，所以，變動空間變動空間需求為需求為0byte，因此，空間複雜度的需求為，因此，空間複雜度的需求為8+0=8bytes1/3/2023811-6.3 演算的效率分析演算的效率分析-排序演算法的比較排序演算法的比較1/3/2023821-6.4 常用的數學式子常用的數學式子1/3/2023831/3/202384
