曾學文 http://www.csie.ntu.edu.tw/~d92005 資料結構 Data Structures 曾學文 http://www.csie.ntu.edu.tw/~d92005.

Presentation on theme: "曾學文 http://www.csie.ntu.edu.tw/~d92005 資料結構 Data Structures 曾學文 http://www.csie.ntu.edu.tw/~d92005."— Presentation transcript:

1 曾學文 http://www.csie.ntu.edu.tw/~d92005
資料結構 Data Structures 曾學文

2 課程內容 I 第1章：資料結構導論（Introduction） 第2章：陣列與結構（Arrays and Structures）
第3章：指標與字串（Pointers and Strings） 第4章：鏈結串列（Linked Lists） 第5章：堆疊（Stacks） 第6章：佇列（Queues） 2008/2/26 Ch01.資料結構導論

3 課程內容 II 第7章：樹與二元樹（Trees and Binary Trees） 第8章：圖形結構（Graphs）
第9章：資料排序（Sorting） 第10章：資料搜尋（Searching） 第11章：堆積（Heaps） 第12章：樹狀搜尋結構（Search Trees） 2008/2/26 Ch01.資料結構導論

4 第1章 資料結構導論 （Introduction）
1-1 資料結構的基礎 1-2 程式設計與演算法 1-3 抽象資料型態ADT 1-4 C語言的模組化程式設計 1-5 遞迴函數 1-6 程式的分析方法 1-7 Big Oh函數 2008/2/26 Ch01.資料結構導論

5 1-1 資料結構的基礎-說明 「資料結構」（Data Structures）是一門計算機科學的基礎學科，其目的是研究程式使用的資料在電腦記憶體的儲存方式，以便撰寫程式處理問題時，能夠使用最佳的資料結構，並且提供一種策略或方法來有效率的善用這些資料，以便達到下列目的，如下所示： 程式執行速度快。 資料佔用最少的記憶空間。 更快速的存取這些資料。 2008/2/26 Ch01.資料結構導論

6 1-1 資料結構的基礎-圖例 上述轉換資料的方法策略就是「演算法」（Algorithms）。
演算法和資料結構的關係非常的密切，因為程式使用的演算法和資料結構都會影響程式的執行效率，換句話說，演算法加上資料結構就等於程式，如下所示： 「演算法」 + 「資料結構」 = 「程式」 2008/2/26 Ch01.資料結構導論

7 1-2 程式設計與演算法 1-2-1 程式設計的過程 1-2-2 演算法 1-2-3 模組化 1-2-4 由上而下的設計方法
2008/2/26 Ch01.資料結構導論

8 1-2-1 程式設計的過程-階段 程式設計是將需要解決的問題轉換成程式碼，程式碼不只能夠在電腦上正確的執行，而且可以驗證程式執行的正確性，程式設計的過程可以分成5個階段，如下所示： 需求（Requirements） 設計（Design） 分析（Analysis） 撰寫程式碼（Coding） 驗證（Verification） 2008/2/26 Ch01.資料結構導論

9 1-2-1 程式設計的過程-需求 需求（Requirements）：程式設計的需求是在了解問題本身，以便確切獲得程式需要輸入的資料和其產生的結果，如下圖所示： 2008/2/26 Ch01.資料結構導論

10 1-2-1 程式設計的過程-設計 設計（Design）：在了解程式設計的需求後，我們就可以開始找尋解決問題的方法和策略，簡單的說，設計階段就是找出解決問題的步驟，如下圖所示： 2008/2/26 Ch01.資料結構導論

11 1-2-1 程式設計的過程-分析 分析（Analysis）：在解決需求時，只有一種解決方法嗎？ 例如：如果有100個變數，
我們可以宣告100個變數(variables)來儲存資料， 或是使用陣列(array)來儲存， 在分析階段是將所有可能解決問題的演算法都寫下來，然後分析比較那一種方法比較好，選擇最好的演算法來撰寫程式。 2008/2/26 Ch01.資料結構導論

12 1-2-1 程式設計的過程-撰寫 撰寫程式碼（Coding）：現在就可以開始使用指定的程式語言來撰寫程式碼，以本課程為例是使用 C 程式語言， 在實際撰寫程式時，可能發現另一種方法比較好，因為設計歸設計，在實際撰寫程式時才能真正發現其優劣， 如果這是一個好的設計方法，就算改為其它方法也不會太困難。 2008/2/26 Ch01.資料結構導論

13 1-2-1 程式設計的過程-驗證 驗證（Verification）：驗證是證明程式執行的結果符合需求的輸出資料，在這個階段可以再細分成三個部分： 證明：執行程式時需要證明它的執行結果是正確的，程式符合所有輸入資料的組合，程式規格也都符合演算法的需求。 測試：程式需要測試各種可能情況、條件和輸入資料，以測試程式執行無誤，如果有錯誤產生，就需要除錯來解決程式問題。 除錯：如果程式無法輸出正確的結果，除錯是在找出錯誤的地方，我們不但需要找出錯誤，還需要決定如何更正它。 2008/2/26 Ch01.資料結構導論

14 1-2-2 演算法-定義 演算法(Algorithms)是完成目標工作的一組指令，這組指令的步驟是有限的。除此之外，演算法還必須滿足一些條件，如下所示： 輸入(Input)：沒有或數個外界的輸入資料。 輸出(Output)：至少有一個輸出結果。 明確性(Definiteness)：每一個指令步驟都十分明確，沒有模稜兩可。 有限性(Finiteness)：這組指令一定結束。 有效性(Effectiveness)：每一個步驟都可行，可以追蹤其結果。 2008/2/26 Ch01.資料結構導論

15 1-2-2 演算法-方法 演算法只是將解決問題步驟詳細的寫出來，所以並沒有固定的方式，基本上只要能夠描述這組指令的執行過程即可，常用的方式如下所示： 一般語言文字：直接使用文字描述來說明執行的步驟。 虛擬碼（Pseudo Code）*：趨近程式語言的描述方法，其每一列約可轉換成一列程式碼。 流程圖（Flow Chart）：使用結構化的圖表描述執行過程，以各種不同形狀的圖形表示不同的操作。 2008/2/26 Ch01.資料結構導論

16 1-2-2 演算法-虛擬碼範例 從數字1加到數字10的演算法的虛擬碼，如下所示： /* 計算1加到10 */ Let counter = 1
Let total = 0 while counter <= 10 total = total + counter Add 1 to counter Output the total /* 顯示結果 */ 2008/2/26 Ch01.資料結構導論

17 1-2-2 演算法-流程圖範例 從1加到10演算法的 流程圖，如右圖所示： 2008/2/26 Ch01.資料結構導論

18 1-2-3 模組化-說明 模組化(Moduling)主要是針對解決問題的方法，把一件大型的工作切割成多個小工作，
切割的工作屬於一種結構化分析的範疇， 最常使用的是「由上而下的設計方法」(Top-Down Design)，其主要是使用程序(procedures)為單位來切割工作，也就是所謂的「程序式程式設計」（Procedural Design）。 2008/2/26 Ch01.資料結構導論

19 1-2-3 模組化-意義1 範例1: 使用一個簡單的數學不等式來說明模組化的意義，如下所示：
C(x)：函數表示問題的複雜度。 E(x)：函數代表需要花費多少工時來解決這個問題。 上述數學函數分別表示問題的複雜度和花費時間，現在有兩個問題P1和P2等待解決，問題P1的複雜度比問題P2高，可以得到不等式，如下所示： C(P1) > C(P2) → E(P1) > E(P2) (1) 上述不等式表示問題P1的工作量比解決問題P2來的費時，因為問題P1比較複雜。 2008/2/26 Ch01.資料結構導論

20 1-2-3 模組化-意義2 接下來，將問題P1和P2合併解決，但是必須考慮兩個問題間的關連性，如此會延伸出更多的問題。所以，可以得到不等式，如下所示： C(P1+P2) > C(P1)+C(P2) 接著從不等式(1)開始推導，可以得到不等式，如下所示： → E(P1+P2) > E(P1)+E(P2) 上述不等式的意義是將一個問題劃分成數個小問題，然後分別解決這些問題的工作量比直接解決一個大問題所需的工作量來的少，這就是模組化的目的。 2008/2/26 Ch01.資料結構導論

21 1-2-4 由上而下的設計方法-說明 由上而下的設計方法（Top-down Design）
是在面對問題時，先考慮將整個解決問題的方法分解成數個大「模組」（Modules）， 然後針對每一個大模組，一一分割成數個小模組，如此一直細分，最後等這些細分小問題的小模組完成後，再將它們組合起來， 如此一層層的向上爬，完成整個軟體系統或應用程式的設計。 例如：玩拼圖遊戲一定會先將整個拼圖粗分為數個區域，等每一個區域都拼好後，整張拼圖也就完成 2008/2/26 Ch01.資料結構導論

22 1-2-4 由上而下的設計方法-注意事項 獨立性：每一個分割模組間的關聯性愈少，處理起來就會愈快。
獨立性是指當處理某一個子問題時，無需考慮到其它子問題。 換句話說，獨立性是要將每一個問題都定義成一件簡單且明確的問題。 結合問題：小心控制子問題間的結合方法，而且要注意結合這些子問題的邏輯順序，避免語焉不詳的結果。 子問題(Sub-problems)間的溝通：雖然獨立性可以減少各問題間的關聯性，但是並無法避免掉全部的溝通。因此各問題間如何溝通的問題（即函數的參數傳遞）也是十分重要的考量。 2008/2/26 Ch01.資料結構導論

23 1-3 抽象資料型態ADT 1-3-1 抽象化 (Abstraction) – 塑模 (Modeling) 1-3-2 程序或函數抽象化
2008/2/26 Ch01.資料結構導論

24 1-3-1 抽象化 – 塑模(說明) 程式設計的目的是解決問題，也就是將現實生活中的真實問題轉換成電腦程式，讓電腦執行程式幫助我們解決問題，這個過程是找出問題的模型，稱為「塑模」（Modeling），使用抽象觀點來檢視問題，以便建立問題的模型，將問題轉換成模型的方式稱為「抽象化」（Abstraction），如下圖所示： 2008/2/26 Ch01.資料結構導論

25 1-3-1 抽象化 – 塑模(定義屬性) 「塑模」（Modeling）的主要的目的是定義問題的二個屬性，如下所示：
資料（Data）：問題影響的資料。 操作（Operators）：問題產生的操作。 例如：學生基本資料的問題，可以抽象化成Students模型， 資料部分是：學號、姓名、地址和電話號碼， 操作部分有：指定和取得學生的姓名、地址和電話號碼。 2008/2/26 Ch01.資料結構導論

26 1-3-2 程序或函數抽象化-說明 程序或函數抽象化（Procedure Abstraction or Function Abstraction）的針對傳統由上而下的程式設計方法， 將問題分割成一個個子工作(Sub-task; Sub-job)，分割的程序或函數並不用考量實作的程式碼，只需定義好程序或函數使用介面的參數和傳回值，將它視為一個黑盒子， 換句話說，程式可以使用任何符合介面的程序或函數來取代，稱為程序或函數抽象化。 2008/2/26 Ch01.資料結構導論

27 1-3-2 程序或函數抽象化-範例 將繪出房屋問題分解成一個個繪圖操作的程序
當定義好<繪出門框程序的使用介面 >後，如果開發出更佳的演算法，只需將程序取代成實作的新程式碼，並不用更改使用介面，就可以增加程式執行效率，如果程序擁有此特性，稱為程序抽象化(Procedure Abstraction)。 2008/2/26 Ch01.資料結構導論

28 1-3-3 抽象資料型態（ADT）-說明 「抽象資料型態」（Abstract Data Type; ADT）是一種自訂資料型態，包含資料(data)和相關操作(operations)，將資料和處理資料的操作一起思考，結合在一起，操作是對外的使用介面，如下圖所示： 2008/2/26 Ch01.資料結構導論

29 1-3-3 抽象資料型態（ADT）-範例 例如：將學生基本資料抽象化成Students抽象資料型態，內含學號id、姓名name、地址address和電話號碼phone等資料，和setStudent()指定學生資料，getName()、getAddress()和getPhone()取出學生資料等操作，如下圖所示： 2008/2/26 Ch01.資料結構導論

30 1-3-3 抽象資料型態（ADT）-實作 以物件導向程式語言：C++或Java語言來說，
Students資料型態就是Students類別，程式可以使用Students類別建立多個Students副本（Instances，副本是物件導向名詞，它就是一個物件），用來模擬真實世界的學生， 例如：同班同學、高中同學和同修一門課的同學等。 雖然C語言不是物件導向程式語言，不過仍然可以使用C語言的模組化程式設計來實作抽象資料型態，其主要的問題是只能建立一個副本，並不能像物件導向程式語言的類別能夠建立多個副本。 2008/2/26 Ch01.資料結構導論

31 1-4 C語言的模組化程式設計-說明 「模組」（Modules）是特定功能的相關資料和函數集合，
程式設計者只需知道模組對外的使用介面（即各模組函數的呼叫方式），就可以使用模組提供的功能， 而不用實際了解模組內部程式碼的實作和內部資料儲存使用的資料結構。 2008/2/26 Ch01.資料結構導論

32 1-4 C語言的模組化程式設計-種類 模組化程式設計（Modular Programming）就是建立相關資料和函數集合的模組，模組主要可以分成兩個部分：介面與實作，如下所示： 模組介面（Module Interface）：模組介面是定義模組函數和使用的資料，即定義讓使用此模組的程式可以呼叫的函數和存取的變數資料，在C語言是使用標頭檔.h定義模組介面。 模組實作（Module Implementations）：模組的實作部分是模組函數和資料的實際程式碼，程式設計者需要定義哪些函數屬於公開介面，哪些只能在模組程式檔使用，C語言的程式檔案.c可以實作模組的程式碼。 2008/2/26 Ch01.資料結構導論

33 1-4 C語言的模組化程式設計-公開與私用關鍵字
extern和static關鍵字來區分公開或內部使用的函數與變數，如下所示： 在標頭檔(header file)宣告成extern的變數和函數：這是可供其它程式使用的外部函數和變數。 在模組程式檔宣告成static的變數和函數：只能在模組程式檔中使用。 2008/2/26 Ch01.資料結構導論

34 1-5 遞迴函數 1-5-1 遞迴的基礎 1-5-2 遞迴的階層函數 2008/2/26 Ch01.資料結構導論

35 1-5 遞迴函數 「遞迴」（Recursive）是程式設計的一個重要觀念。
「遞迴函數」（Recursive Functions）可以讓函數的程式碼變的很簡潔，但是設計這類函數需要很小心，不然很容易就掉入類似無窮迴圈的陷阱。 2008/2/26 Ch01.資料結構導論

36 1-5-1 遞迴的基礎-說明 遞迴的觀念主要是在建立遞迴函數，其基本定義，如下所示：
一個問題的內涵是由本身所定義的話，稱之為遞迴。 遞迴函數是由上而下分析方法的一種特殊的情況，因為子問題本身和原來問題擁有相同的特性，只是範圍改變，範圍逐漸縮小到一個終止條件。 2008/2/26 Ch01.資料結構導論

37 1-5-1 遞迴的基礎-特性 遞迴函數的特性，如下所示： 遞迴函數在每次呼叫時，都可以使問題範圍逐漸縮小。(收斂)
函數需要擁有一個終止條件，以便結束遞迴函數的執行，否則遞迴函數並不會結束，而是持續的呼叫自已。(無窮回圈) 2008/2/26 Ch01.資料結構導論

38 1-5-2 遞迴的階層函數-公式 遞迴函數最常見的應用是數學的階層函數n!，如下所示： 2008/2/26 Ch01.資料結構導論

39 1-5-2 遞迴的階層函數-範例 例如：計算4!的值，從上述定義n>0，使用n!定義的第2條計算階層函數4!的值，如下所示：
4!=4*3*2*1=24 4!=4*(4-1)!=4*3! 3! = 3*(3-1)! = 3*2! 2! = 2*(2-1)! = 2*1! 1! = 1*(1-1)! = 1*0! = 1*1 = 1 在知道1!的值後，就可以計算出2!~4!的值，如下所示： 2! = 2*(2-1)! = 2*1! = 2 3! = 3(3-1)! = 3*2! = 3*2 = 6 4! = 4*(4-1)! = 4*3! = 24 2008/2/26 Ch01.資料結構導論

40 遞迴函式 利用遞迴函式求n! (a) 遞迴呼叫的順序 (b) 遞迴值的回傳順序 #include<iostream>
5! (a) 遞迴呼叫的順序 (b) 遞迴值的回傳順序 最後值 = 120 回傳 5! = 5 * 24 = 120 回傳 4! = 4 * 6 = 24 回傳 2! = 2 * 1 = 2 回傳 3! = 3 * 2 = 6 回傳 1 5 * 4! 1 4 * 3! 3 * 2! 2 * 1! #include<iostream> using namespace std; int xxx(int a) { if (a==o) return 1; else return a*xxx(a-1); } void main() int b; cin>>b; cout<<xxx(b)<<endl; 利用遞迴函式求n!

41 Ex:遞減的code #include<iostream> using namespace std;
int xxx(int a) { if (a==o) return 1; else return a*xxx(a-1); } void main() int b; cin>>b; cout<<xxx(b)<<endl;

42 1-6 程式的分析方法 1-6-1 空間與時間複雜度 1-6-2 頻率計數的計算 1-6-3 遞迴函數的頻率計數 2008/2/26
Ch01.資料結構導論

43 1-6 程式的分析方法 一個好程式需要滿足一些條件，如下所示： 正確的執行結果：程式滿足分析的輸入和輸出結果。
可維護性高：程式不只需要正確，而且是可讀、容易修改和擴充，這屬於程式設計方法和風格的問題， 例如：使用模組化來設計程式和加上完整程式註解的說明。 執行效率高：執行效率是指程式執行花費的時間和所需的記憶體空間， 一般來說，這兩項在大多數情況是矛盾的，因為使用較大的記憶體空間，通常可以換取程式執行效率的改進，反之亦然，至於如何找到其間的平衡點，就需視解決的問題而定。 2008/2/26 Ch01.資料結構導論

44 1-6-1 空間與時間複雜度-說明 程式或演算法的執行效率分析可以分為程式執行所需記憶體的「空間複雜度」（Space Complexity），和所需時間的「時間複雜度」（Time Complexity）分析。 2008/2/26 Ch01.資料結構導論

45 1-6-1 空間與時間複雜度-空間複雜度分析 空間複雜度是指程式執行時所需的記憶體空間，主要分成兩種，如下所示：
固定記憶體空間：程式本身、靜態變數和常數等所佔用的記憶體空間，它和程式輸出入的資料量並沒有關係。 動態記憶體空間：在程式執行過程所需的額外記憶體空間， 例如：函數參數、遞迴函數的堆疊空間和程式動態配置的記憶體空間等。它會隨著輸出入的資料量、函數參數個數，遞迴呼叫次數而動態改變所需的記憶體空間。 2008/2/26 Ch01.資料結構導論

46 1-6-1 空間與時間複雜度-時間複雜度分析(說明)
程式執行效率就是在計算程式執行的時間，例如：在程式中有一列程式碼，如下所示： a = a + 1; 上述程式碼將變數a的值加1。如果使用for迴圈執行此程式碼n次，如下所示： for ( i = 0; i < n ; i++ ) a = a + 1; 上述程式碼執行的全部時間是n*t，t為單獨執行a = a + 1程式碼所需的時間。 2008/2/26 Ch01.資料結構導論

47 1-6-1 空間與時間複雜度-時間複雜度分析(時間t)
執行程式碼使用的電腦種類：桌上型電腦、工作站或大型電腦。 CPU使用的機器語言指令集：某些CPU的機器語言指令包含乘法和除法指令，有些沒有，有些以硬體實作，有些是軟體加持。 CPU執行機器語言指令所需的時間：即CPU的執行速度，每秒可以執行的指令數不同，執行所需的時間當然不同。 使用的編譯程式：好的編譯程式可以將指令轉譯成為單一機器語言指令，相對於將它轉譯成數個機器語言指令的編譯程式，其執行時間的差異就十分明顯。 2008/2/26 Ch01.資料結構導論

48 1-6-1 空間與時間複雜度-時間複雜度分析(頻率計數)
基於上述原因，執行單位時間t依不同軟硬體，可能造成十分大的差異， 因此我們並不會直接計算程式的執行時間，取而代之是計算程式每一列程式碼的執行頻率， 也就是「頻率計數」（Frequency Count），以程式執行的次數來代替每一列程式碼實際執行的時間。 2008/2/26 Ch01.資料結構導論

49 1-6-2 頻率計數的計算-說明 頻率計數（Frequency Count） 是以原始程式碼的每一列可執行指令作為一個執行單位，
我們可以計算出程式的執行次數，這個次數就是頻率計數。 2008/2/26 Ch01.資料結構導論

50 1-6-2 頻率計數的計算-種類 2008/2/26 Ch01.資料結構導論

51 1-6-2 頻率計數的計算-陣列元素和(函數) 函數sumArray()可以計算參數陣列元素的總和，函數程式碼如下所示：
01: int sumArray(int *data, int n) { 02: int i, total = 0;//宣告整數變數 03: for ( i = 0; i < n; i++ ) 04: total += data[i]; 05: return total; 06: } 2008/2/26 Ch01.資料結構導論

52 1-6-2 頻率計數的計算-陣列元素和(頻率計數)
函數頻率計數主要是在for迴圈，此迴圈共執行n次，第2列的頻率計數1是因為total = 0，第3列因為最後一次跳出迴圈時仍會進行比較，所以為n+1。 函數sumArray()的頻率計數為各列計數的總和：1+(n+1)+n+1 = 2n+3。 2008/2/26 Ch01.資料結構導論

53 1-6-2 頻率計數的計算-循序搜尋(函數) 函數sequential()是從陣列第1個元素開始，找尋陣列是否擁有指定的元素，函數程式碼如下所示： 01: int sequential(int *data, int n, int target) { 02: int i; /* 變數宣告 */ 03: for ( i = 0; i < n; i++ ) /* 搜尋迴圈 */ 04: /* 比較是否是鍵值 */ 05: if ( data[i] == target ) 06: return i; 07: return -1; 08: } 2008/2/26 Ch01.資料結構導論

54 1-6-2 頻率計數的計算-循序搜尋(頻率計數)
函數的頻率計數不包含變數i宣告和第4列註解，主要是for迴圈和if條件，迴圈共執行n次，頻率計數可以分成兩種情況，如下所示： 找到鍵值：因為找到鍵值，所以迴圈不會執行到最後一次跳出迴圈，此時第3列的計數是n（n是找到鍵值前的比較次數，而不是迴圈執行次數），跳出後執行第6列，並不會執行第7列，其頻率計數是0 + n n + 1 = 2n+1。 沒有找到鍵值：此為最壞情況，需要執行完整個for迴圈，此時是執行第7列，其頻率計數是0 + (n + 1) n + 1 = 2n+2。 2008/2/26 Ch01.資料結構導論

55 1-6-2 頻率計數的計算-費氏數列(說明) 費氏數列（Fibonacci）是一序列的數值，從第3項開始每一項接著的數值都是前兩個數值的和，如下所示： 0,1,1,2,3,5,8,13,21,34……. 上述費氏數列的第1項為F0，可以得到F0=0，F1=1和F2 = F0 + F1 = 1，依序類推，其公式如下所示： Fn = Fn-1 + Fn-2，n≧2 2008/2/26 Ch01.資料結構導論

56 1-6-2 頻率計數的計算-費氏數列(函數) 01: void fibonacci(int n) {
02: int fn; /* F(n)變數 */ 03: int fn2; /* F(n-2)變數 */ 04: int fn1; /* F(n-1)變數 */ 05: int i; 06: if ( n <= 1 ) /* 項數是否小於1 */ 07: printf("F%d=[%d]\n", n, n); /* 顯示項目 */ 08: else { 09: fn2 = 0; /* 設定 F(n-2) */ 10: fn1 = 1; /* 設定 F(n-1) */ 11: for ( i = 2; i <= n; i++ ) {/* 顯示數列的迴圈 */ 12: fn = fn2 + fn1; /* 計算各一般項 */ 13: fn2 = fn1; /* 重設 F(n-2) */ 14: fn1 = fn; /* 重設 F(n-1) */ 15: } 16: printf("F%d=[%d]\n", n, fn);/* 顯示項目 */ 17: } 18: } 2008/2/26 Ch01.資料結構導論

57 1-6-2 頻率計數的計算-費氏數列(頻率計數1)
函數第2~5列的變數宣告並不計算，程式區塊的左右大括號和else也不列入計算，for迴圈執行n-1次。函數fibonacci()可執行程式碼的頻率計數，如下表所示： 2008/2/26 Ch01.資料結構導論

58 1-6-2 頻率計數的計算-費氏數列(頻率計數2)
函數fibonacci()的頻率計數計算需要考慮兩種情況，如下所示： n = 0或1：執行函數第6和7列共2列程式碼，所以頻率計數是2。 n > 1： 在執行函數第6列的if判斷後，頻率計數是1， 然後執行第9~10列後，目前的頻率計數和為3， 接著執行第11~14列的for迴圈，第11列執行n次（for迴圈共執行n-1次，再加上最後一次比較跳出for迴圈），第12~14列執行3*(n-1) = 3n-3次，目前是4n， 最後第16列可以計算出頻率計數是4n + 1。 2008/2/26 Ch01.資料結構導論

59 1-6-3 遞迴函數的頻率計數-函數 遞迴函數的頻率計數因為函數會呼叫自己本身，其頻率計數類似迴圈敘述，例如：第1-5-2節階層函數的factorial()遞迴函數，如下所示： 01: long factorial(int n) { 02: if ( n == 1 ) /* 終止條件 */ 03: return 1; 04: else 05: return n * factorial(n-1); 06: } 2008/2/26 Ch01.資料結構導論

60 1-6-3 遞迴函數的頻率計數-頻率計數 頻率計數的計算，如下所示：
第5列：函數本身呼叫遞迴函數共n-1次，所以執行n-1次的比較，再加上主程式呼叫遞迴函數時的第1次比較，一共執行n-1+1次，所以頻率計數是n。 第3列：函數只有在最後一次遞迴呼叫才執行，所以頻率計數是1。 第5列後半：函數本身遞迴呼叫共n-1次，所以頻率計數是n-1。 遞迴函數factorial()總共的頻率計數是n n - 1 = 2n。 2008/2/26 Ch01.資料結構導論

61 1-7 Big Oh函數 1-7-1 Big Oh函數的基礎 1-7-2 Big Oh函數的等級 2008/2/26 Ch01.資料結構導論

62 1-7-1 Big Oh函數的基礎-說明 函數O()代表參數頻率計數多項式的級數，唸成Big Oh。
O(n)表示頻率計數是an+b， O(n2)表示頻率計數是an2+bn+c，a、b和c是常數， O()函數不計頻率計數的常數，只取其最高次方的項目，所以是O(1)、O(n)和O(n2)。 例如：費氏數列fibonacci()函數頻率計數的O()函數，如下所示： n=0或1：2 O(1) n>1：4n+1 O(n) 上述頻率計數4n+1是O(n)，因為當n很大時，係數4和1可以不用考慮，O(n)表示程式執行的頻率計數和n成正比。 2008/2/26 Ch01.資料結構導論

63 1-7-1 Big Oh函數的基礎-O(1) O(1)：單行程式碼
a = a + 1; 上述程式碼a = a + 1是一列單行程式碼，不包含在任何迴圈中，頻率計數是1所以是O(1)。 2008/2/26 Ch01.資料結構導論

64 1-7-1 Big Oh函數的基礎-O(n) O(n)：線性迴圈
a = 0; for ( i = 0; i < n; i++ ) a=a+1; 上述程式碼執行n次的a = a + 1，其頻率計數是n+1，包含最後1次的比較，不計常數所以是O(n)。 2008/2/26 Ch01.資料結構導論

65 1-7-1 Big Oh函數的基礎-O(Log n)
a = 0; for ( i = n; i > 0; i = i / 2 ) a=a+1; 或 for ( i = 0; i < n; i = i * 2 ) 上述兩個迴圈的增量是除以2或乘以2，以除法來說，如果n = 16，迴圈依序為8、4、2、1，其執行次數是對數Log n，其頻率計數是Log n+1，包含最後1次的比較，不計常數所以是O(Log n)。 2008/2/26 Ch01.資料結構導論

66 1-7-1 Big Oh函數的基礎-O(nLog n)
a = 0; for ( i = 0; i < n; i++ ) for ( j = n; j > 0; j = j / 2 ) a=a+1; 上述巢狀迴圈的外層是線性迴圈的O(n)，內層是非線性迴圈的O(Log n)，所以是： O(n) * O(Log n) = O(n Log n) 2008/2/26 Ch01.資料結構導論

67 1-7-1 Big Oh函數的基礎-O(n2) O(n2)：巢狀迴圈
a = 0; for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) a=a+1; 上述巢狀迴圈的外層是線性迴圈的O(n)，內層線性迴圈的O(n)，所以是： O(n) * O(n) = O(n2) 2008/2/26 Ch01.資料結構導論

68 1-7-2 Big Oh函數的等級-說明 程式執行效率的時間複雜度可以使用O(1)、O(Log n)、O(n)、O(n Log n)、O(n2)、O(n3)和O(2n)的Big Oh函數來表示，如下表所示： 2008/2/26 Ch01.資料結構導論

69 1-7-2 Big Oh函數的等級-成長曲線圖 2008/2/26 Ch01.資料結構導論

70 1-7-2 Big Oh函數的等級-比較 換句話說，如果一個問題有兩種不同演算法，第一種方法的頻率計數是5n，第二種方法的頻率計數是n2/2，我們可以計算頻率計數與n值的關係，如下表所示： 2008/2/26 Ch01.資料結構導論

71 1-7-2 Big Oh函數的等級-比較說明 當n < 10時，第二種方法比第一種有效率，如果n > 10時，第一種方法反而比較有效率，函數O()分別為O(n)和O(n2)。 所以，當n足夠大時，頻率計數的常數就可忽略不計，只需比較其級數，所以O(n)執行效率比O(n2)好。如果n很小時，常數才需要加以考量，如此才能真正比較程式執行效率的優劣。 2008/2/26 Ch01.資料結構導論