第1章结构导论(Introduction)课件.ppt

1、第第1章章 資料結構導論（資料結構導論（Introduction）n 1-1 資料結構的基礎n 1-2 程式設計與演算法n 1-3 抽象資料型態ADTn 1-4 C語言的模組化程式設計n 1-5 遞迴函數n 1-6 程式的分析方法n 1-7 Big Oh函數1-1 資料結構的基礎資料結構的基礎-說明說明n 資料結構（Data Structures）是一門計算機科學的基礎學科，其目的是研究程式使用的資料在電腦記憶體的儲存方式，以便撰寫程式處理問題時，能夠使用最佳的資料結構，並且提供一種策略或方法來有效率的善用這些資料，以便達到下列目的，如下所示：程式執行速度快。資料佔用最少的記憶空間。更快速的存

2、取這些資料。1-1 資料結構的基礎資料結構的基礎-圖例圖例n 策略或方法是指如何選擇最恰當的資料結構，並且將這些資料轉換成有用的資訊，轉換資料的方法就是演算法（Algorithms），如下圖所示：n 演算法和資料結構的關係非常的密切，因為程式使用的演算法和資料結構都會影響程式的執行效率，換句話說，演算法加上資料結構就等於程式，如下所示：演算法+資料結構=程式main()int largest=0;if(25 largest)largest=25;if(30 largest)largest=30;if(18 largest)largest=18;if(7 largest)largest=7;if

3、(10 largest)largest=10;printf(最大數為%d,largest);範例範例 1:找出最大數找出最大數01:main()02:03:int i;04:int list5=25,30,18,7,10;05:int largest=0;06:for(i=0;i largest)largest=listi;08:printf(最大數為%d,largest);09:範例範例 2:找出最大數找出最大數Difference between the above two?nHow data structure affects your program?nWhich one is bet

4、ter?Why?nWhich one would be potentially faster?Why?Lets review some basics before answering the above questions The Von Neumann Model&Memory AccessQ1:How fast is your CPU?Q2:How is your DIMMs access latency?Q3:What conclusion can be drawn from them?Q4:Where does your program stored?CPU vs Memory Spe

5、edn Clock cycle of a 2GHz CPU 1/(2*109)=0.5 ns In case 4 clocks per instruction 2 nsHow about int sum=i+j;n DDR2-800 1/(400*106)=2.5 ns In case CL=6 6*2.5 ns=15 nsFor a WORD accessn Cache1-2 程式設計與演算法程式設計與演算法n 1-2-1 程式設計的過程n 1-2-2 演算法n 1-2-3 模組化n 1-2-4 由上而下的設計方法1-2-1 程式設計的過程程式設計的過程-階段階段n 程式設計是將需要解決的問

6、題轉換成程式碼，程式碼不只能夠在電腦上正確的執行，而且可以驗證程式執行的正確性，程式設計的過程可以分成5個階段，如下所示：需求（需求（Requirements）設計（設計（Design）分析（分析（Analysis）撰寫程式碼（撰寫程式碼（Coding）驗證（驗證（Verification）1-2-1 程式設計的過程程式設計的過程-需求需求n 需求（需求（Requirements）：）：程式設計的需求是在了解問題本身，以便確切獲得程式需要輸入的資料和其產生的結果，如下圖所示：1-2-1 程式設計的過程程式設計的過程-設計設計n 設計（設計（Design）：）：在了解程式設計的需求後，我們就可以

7、開始找尋解決問題的方法和策略，簡單的說，設計階段就是找出解決問題的步驟，如下圖所示：1-2-1 程式設計的過程程式設計的過程-分析分析n 分析（分析（Analysis）：）：在解決需求時，只有一種解決方法嗎？例如：如果有100個變數，我們可以宣告100個變數來儲存資料，或是使用陣列來儲存，在分析階段是將所有可能解決問題的演算法都寫下來，然後分析比較那一種方法比較好，選擇最好的演算法來撰寫程式。1-2-1 程式設計的過程程式設計的過程-撰寫撰寫n 撰寫程式碼（撰寫程式碼（Coding）：）：現在就可以開始使用指定的程式語言來撰寫程式碼，以本書為例是使用C程式語言，在實際撰寫程式時，可能發現另一種

8、方法比較好，因為設計歸設計，在實際撰寫程式時才能真正發現其優劣，如果這是一個良好的設計方法，就算改為其它方法也不會太困難。1-2-1 程式設計的過程程式設計的過程-驗證驗證n 驗證（驗證（Verification）：）：驗證是證明程式執行的結果符合需求的輸出資料，在這個階段可以再細分成三個部分：證明：證明：執行程式時需要證明它的執行結果是正確的，程式符合所有輸入資料的組合，程式規格也都符合演算法的需求。測試：測試：程式需要測試各種可能情況、條件和輸入資料，以測試程式執行無誤，如果有錯誤產生，就需要除錯來解決程式問題。除錯：除錯：如果程式無法輸出正確的結果，除錯是在找出錯誤的地方，我們不但需要找

9、出錯誤，還需要決定如何更正它。1-2-2 演算法演算法-定義定義n 演算法是完成目標工作的一組指令，這組指令的步驟是有限的。除此之外，演算法還必須滿足一些條件，如下所示：輸入輸入(Input)：沒有或數個外界的輸入資料。輸出輸出(Output)：至少有一個輸出結果。明確性明確性(Definiteness)：每一個指令步驟都十分明確，沒有模稜兩可。有限性有限性(Finiteness)：這組指令一定結束。有效性有效性(Effectiveness)：每一個步驟都可行，可以追蹤其結果。1-2-2 演算法演算法-方法方法n 演算法只是將解決問題步驟詳細的寫出來，所以並沒有固定的方式，基本上只要能夠描述這

10、組指令的執行過程即可，常用的方式如下所示：一般語言文字：一般語言文字：直接使用文字描述來說明執行的步驟 虛擬碼（虛擬碼（Pseudo Code）：）：趨近程式語言的描述方法，其每一列約可轉換成一列程式碼。流程圖（流程圖（Flow Chart）：）：使用結構化的圖表描述執行過程，以各種不同形狀的圖形表示不同的操作。1-2-2 演算法演算法-虛擬碼範例虛擬碼範例n 從1加到10演算法的虛擬碼，如下所示：/*計算1加到10*/Let counter=1Let total=0while counter C(P2)E(P1)E(P2)(1)n 上述不等式表示問題P1的工作量比解決問題P2來的費時，因為問

11、題P1比較複雜。1-2-3 模組化模組化-意義意義2n 接下來，將問題P1和P2合併解決，但是必須考慮兩個問題間的關連性，如此會延伸出更多的問題。所以，可以得到不等式，如下所示：C(P1+P2)C(P1)+C(P2)n 接著從不等式(1)開始推導，可以得到不等式，如下所示：C(P1+P2)C(P1)+C(P2)E(P1+P2)E(P1)+E(P2)n 上述不等式的意義是將一個問題劃分成數個小問題，然後分別解決這些問題的工作量比直接解決一個大問題所需的工作量來的少，這就是模組化的目的。1-2-4 由上而下的設計方法由上而下的設計方法-說明說明n 由上而下的設計方法（Top-down Design

12、）是在面對問題時，先考慮將整個解決問題的方法分解成數個大模組（Modules），然後針對每一個大模組，一一分割成數個小模組，如此一直細分，最後等這些細分小問題的小模組完成後，再將它們組合起來，如此一層層的向上爬，完成整個軟體系統或應用程式的設計。n 例如：玩拼圖遊戲一定會先將整個拼圖粗分為數個區域，等每一個區域都拼好後，整張拼圖也就完成1-2-4 由上而下的設計方法由上而下的設計方法-注意事項注意事項n 獨立性：獨立性：每一個分割模組間的關聯性愈少，處理起來就會愈快。所謂獨立性，是指當處理某一個子問題時，無需考慮到其它子問題。換一句話說，獨立性是要將每一個問題都定義成一件簡單且明確的問題。n

13、結合問題：結合問題：小心控制子問題間的結合方法，而且要注意結合這些子問題的邏輯順序，避免語焉不詳的結果。n 子問題間的溝通：子問題間的溝通：雖然獨立性可以減少各問題間的關聯性，但是並無法避免掉全部的溝通。因此各問題間如何溝通的問題（即函數的參數傳遞）也是十分重要的考量。1-3 抽象資料型態抽象資料型態ADTn 1-3-1 抽象化 塑模n 1-3-2 程序或函數抽象化n 1-3-3 抽象資料型態（ADT）1-3-1 抽象化抽象化 塑模塑模(說明說明)n 程式設計的目的是解決問題，也就是將現實生活中的真實問題轉換成電腦程式，讓電腦執行程式幫助我們解決問題，這個過程是找出問題的模型，稱為塑模（Mod

14、eling），使用抽象觀點來檢視問題，以便建立問題的模型，將問題轉換成模型的方式稱為抽象化（Abstraction），如下圖所示：1-3-1 抽象化抽象化 塑模塑模(定義屬性定義屬性)n 塑模（Modeling）的主要的目的是定義問題的二個屬性，如下所示：資料（資料（Data）：）：問題影響的資料。操作（操作（Operators）：）：問題產生的操作。n 例如：學生基本資料的問題，可以抽象化成Students模型，資料部分是：學號、姓名、地址和電話號碼，操作部分有：指定和取得學生的姓名、地址和電話號碼。1-3-2 程序或函數抽象化程序或函數抽象化-說明說明n 程序或函數抽象化（Procedur

15、e Abstraction or Function Abstraction）的針對傳統由上而下的程式設計方法，將問題分割成一個個子工作，分割的程序或函數並不用考量實作的程式碼，只需定義好程序或函數使用介面的參數和傳回值，將它視為一個黑盒子，換句話說，程式可以使用任何符合介面的程序或函數來取代，稱為程序或函數抽象化。1-3-2 程序或函數抽象化程序或函數抽象化-範例範例n 當定義繪出門框程序的使用介面後，如果開發出更佳的演算法，只需將程序取代成實作的新程式碼，並不用更改使用介面，就可以增加程式執行效率，如果程序擁有此特性，稱為程序抽象化。1-3-3 抽象資料型態（抽象資料型態（ADT）-說明說明

16、n 抽象資料型態（Abstract Data Type）是一種自訂資料型態，包含資料和相關操作，將資料和處理資料的操作一起思考，結合在一起，操作是對外的使用介面，如下圖所示：1-3-3 抽象資料型態（抽象資料型態（ADT）-範例範例n 例如：將學生基本資料抽象化成Students抽象資料型態，內含學號id、姓名name、地址address和電話號碼phone等資料，和setStudent()指定學生資料，getName()、getAddress()和getPhone()取出學生資料等操作，如下圖所示：1-3-3 抽象資料型態（抽象資料型態（ADT）-實作實作n 以物件導向程式語言：C+或Jav

17、a語言來說，Students資料型態就是Students類別，程式可以使用Students類別建立多個Students副本（Instances，副本是物件導向名詞，它就是一個物件），用來模擬真實世界的學生，例如：同班同學、高中同學和同修一門課的同學等。n 雖然C語言不是物件導向程式語言，不過仍然可以使用C語言的模組化程式設計來實作抽象資料型態，其主要的問題是只能建立一個副本，並不能像物件導向程式語言的類別能夠建立多個副本。1-4 C語言的模組化程式設計語言的模組化程式設計-說明說明n 模組（Modules）是特定功能的相關資料和函數集合，程式設計者只需知道模組對外的使用介面（即各模組函數的呼叫

18、方式），就可以使用模組提供的功能，而不用實際了解模組內部程式碼的實作和內部資料儲存使用的資料結構。1-4 C語言的模組化程式設計語言的模組化程式設計-種類種類n 模組化程式設計（Modular Programming）就是建立相關資料和函數集合的模組，模組主要可以分成兩個部分：介面與實作，如下所示：模組介面（模組介面（Module Interface）：）：模組介面是定義模組函數和使用的資料，即定義讓使用此模組的程式可以呼叫的函數和存取的變數資料，在C語言是使用標頭檔.h定義模組介面。模組實作（模組實作（Module Implementations）：）：模組的實作部分是模組函數和資料的實際程

19、式碼，程式設計者需要定義哪些函數屬於公開介面，哪些只能在模組程式檔使用，C語言的程式檔案.c可以實作模組的程式碼。1-4 C語言的模組化程式設計語言的模組化程式設計-公開與私用關鍵字公開與私用關鍵字n extern和static關鍵字來區分公開或內部使用的函數與變數，如下所示：在標頭檔宣告成extern的變數和函數：這是可供其它程式使用的外部函數和變數。在模組程式檔宣告成static的變數和函數：只能在模組程式檔中使用。1-5 遞迴函數遞迴函數n 1-5-1 遞迴的基礎n 1-5-2 遞迴的階層函數1-5-1 遞迴的基礎遞迴的基礎-說明說明n 遞迴（Recursion）是程式設計上一個非常重要

20、的觀念，可以幫助我們建立簡潔的程式碼來解決程式問題。n 遞迴觀念的主要目的是建立遞迴函數（Recursive Functions），遞迴可以讓函數的程式碼變的很簡潔，但是設計遞迴函數需要很小心，不然很容易就掉入類似無窮迴圈的陷阱。1-5-1 遞迴的基礎遞迴的基礎-定義定義n 遞迴的觀念主要是在建立遞迴函數，其基本定義，如下所示：一個問題的內涵是由本身所定義的話，稱之為遞迴。n 遞迴函數是由上而下分析方法的一種特殊的情況，因為子問題本身和原來問題擁有相同的特性，只是範圍改變，範圍逐漸縮小到一個終止條件。1-5-1 遞迴的基礎遞迴的基礎-特性特性n 遞迴函數的特性，如下所示：遞迴函數在每次呼叫時，

21、都可以使問題範圍逐漸縮小。函數需要擁有一個終止條件，以便結束遞迴函數的執行，否則遞迴函數並不會結束，而是持續的呼叫自已。1-5-1 遞迴的基礎遞迴的基礎-種類種類1n 直接遞迴（直接遞迴（Direct Recursion）：）：遞迴函數是在遞迴函數本身的程式碼進行呼叫，也就是自己呼叫自己，稱為直接遞迴，如下所示：void A().A();.1-5-1 遞迴的基礎遞迴的基礎-種類種類2n 間接遞迴（間接遞迴（Indirect Recursion）：）：間接遞迴至少需要2個函數A()和B()，在函數A()的程式碼呼叫函數B()；函數B()的程式碼呼叫函數A()，此情況的遞迴呼叫稱為間接遞迴，如下所

22、示：void A().B();.void B().A();.1-5-2 遞迴的階層函數遞迴的階層函數-公式公式n 遞迴函數最常見的應用是數學的階層函數n!，如下所示：1-5-2 遞迴的階層函數遞迴的階層函數-範例範例n 例如：計算4!的值，從上述定義n0，使用n!定義的第2條計算階層函數4!的值，如下所示：4!=4*3*2*1=244!=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=1n 在知道1!的值後，就可以計算出2!4!的值，如下所示：2!=2*(2-1)!=2*1!=23!=3*(3-1)!=3*2!

23、=3*2=64!=4*(4-1)!=4*3!=241-6 程式的分析方法程式的分析方法n 1-6-1 空間與時間複雜度n 1-6-2 頻率計數的計算n 1-6-3 遞迴函數的頻率計數1-6 程式的分析方法程式的分析方法n 一個好程式需要滿足一些條件，如下所示：正確的執行結果：正確的執行結果：程式滿足分析的輸入和輸出結果。可維護性高：可維護性高：程式不只需要正確，而且是可讀、容易修改和擴充，這屬於程式設計方法和風格的問題，例如：使用模組化來設計程式和加上完整程式註解的說明。執行效率高：執行效率高：執行效率是指程式執行花費的時間和所需的記憶體空間，一般來說，這兩項在大多數情況是矛盾的，因為使用較大

24、的記憶體空間，通常可以換取程式執行效率的改進，反之亦然，至於如何找到其間的平衡點，就需視解決的問題而定。1-6-1 空間與時間複雜度空間與時間複雜度-說明說明n 程式或演算法的執行效率分析可以分為程式執行所需記憶體的空間複雜度（Space Complexity），和所需時間的時間複雜度（Time Complexity）分析。1-6-1 空間與時間複雜度空間與時間複雜度-空間複雜度分析空間複雜度分析n 空間複雜度是指程式執行時所需的記憶體空間，主要分成兩種，如下所示：固定記憶體空間：固定記憶體空間：程式本身、靜態變數和常數等所佔用的記憶體空間，它和程式輸出入的資料量並沒有關係。動態記憶體空間：動

25、態記憶體空間：在程式執行過程所需的額外記憶體空間，例如：函數參數、遞迴函數的堆疊空間和程式動態配置的記憶體空間等。它會隨著輸出入的資料量、函數參數個數，遞迴呼叫次數而動態改變所需的記憶體空間。1-6-1 空間與時間複雜度空間與時間複雜度-時間複雜度分析時間複雜度分析(說明說明)n 程式執行效率就是在計算程式執行的時間，例如：在程式中有一列程式碼，如下所示：a=a+1;n 上述程式碼將變數a的值加1。如果使用for迴圈執行此程式碼n次，如下所示：for(i=0;i n;i+)a=a+1;n 上述程式碼執行的全部時間是n*t，t為單獨執行a=a+1程式碼所需的時間。1-6-1 空間與時間複雜度空間

26、與時間複雜度-時間複雜度分析時間複雜度分析(時間時間t)n 至於如何決定時間t，其評量標準如下所示：執行程式碼使用的電腦種類：執行程式碼使用的電腦種類：桌上型電腦、工作站或大型電腦。CPU使用的機器語言指令集：使用的機器語言指令集：某些CPU的機器語言指令包含乘法和除法指令，有些沒有，有些以硬體實作，有些是軟體加持。CPU執行機器語言指令所需的時間：執行機器語言指令所需的時間：即CPU的執行速度，每秒可以執行的指令數不同，執行所需的時間當然不同。使用的編譯程式：使用的編譯程式：好的編譯程式可以將指令轉譯成為單一機器語言指令，相對於將它轉譯成數個機器語言指令的編譯程式，其執行時間的差異就十分明顯

27、。1-6-1 空間與時間複雜度空間與時間複雜度-時間複雜度分析時間複雜度分析(頻率計數頻率計數)n 基於上述原因，執行單位時間t依不同軟硬體，可能造成十分大的差異，因此我們並不會直接計算程式的執行時間，取而代之是計算程式每一列程式碼的執行頻率，也就是頻率計數（Frequency Count），以程式執行的次數來代替每一列程式碼實際執行的時間。1-6-2 頻率計數的計算頻率計數的計算-說明說明n 頻率計數（Frequency Count）是以原始程式碼的每一列可執行指令作為一個執行單位，我們可以計算出程式的執行次數，這個次數就是頻率計數。1-6-2 頻率計數的計算頻率計數的計算-種類種類種類種類

28、頻率計數頻率計數說明說明註解0註解是不可執行的程式碼宣告程式碼0宣告程式碼也是不可執行的程式碼，例如：變數宣告，程式區塊的大括號指定敘述和運算式1不含函數呼叫的指定敘述和運算式執行函數1函數執行次數是 1，遞迴函數需視其遞迴執行的次數而定條件敘述視情況if、switch 條件敘述的頻率計數是條件運算式本身的判斷次數，和程式區塊中程式碼頻率計數的總和迴圈敘述視情況for、while 和 do/while 迴圈敘述的頻率計數分為控制部分（即迴圈條件）和程式區塊，如果迴圈執行 n 次，則控制部分為 n+1 次（多一次結束迴圈的判斷），程式區塊是 n 次1-6-2 頻率計數的計算頻率計數的計算-陣列元

29、素和陣列元素和(函數函數)n 函數sumArray()可以計算參數陣列元素的總和，函數程式碼如下所示：01:int sumArray(int*data,int n)02:int i,total=0;03:for(i=0;i n;i+)04:total+=datai;05:return total;06:1-6-2 頻率計數的計算頻率計數的計算-陣列元素和陣列元素和(頻率計數頻率計數)n 函數頻率計數主要是在for迴圈，此迴圈共執行n次，第2列的頻率計數1是因為total=0，第3列因為最後一次跳出迴圈時仍會進行比較，所以為n+1。n 函數sumArray()的頻率計數為各列計數的總和：2n+3

30、。1-6-2 頻率計數的計算頻率計數的計算-循序搜尋循序搜尋(函數函數)n 函數sequential()是從陣列第1個元素開始，找尋陣列是否擁有指定的元素，函數程式碼如下所示：01:int sequential(int*data,int n,int target)02:int i;/*變數宣告*/03:for(i=0;i n;i+)/*搜尋迴圈*/04:/*比較是否是鍵值*/05:if(datai=target)06:return i;07:return-1;08:1-6-2 頻率計數的計算頻率計數的計算-循序搜尋循序搜尋(頻率計數頻率計數)n 函數的頻率計數不包含變數i宣告和第4列註解，主要

31、是for迴圈和if條件，迴圈共執行n次，頻率計數可以分成兩種情況，如下所示：找到鍵值：因為找到鍵值，所以迴圈不會執行到最後一次跳出迴圈，此時第3列的計數是n（n是找到鍵值前的比較次數，而不是迴圈執行次數），跳出後執行第6列，並不會執行第7列，其頻率計數是0+n+0+n+1=2n+1。沒有找到鍵值：此為最壞情況，需要執行完整個for迴圈，此時是執行第7列，其頻率計數是0+(n+1)+0+n+1=2n+2。1-6-2 頻率計數的計算頻率計數的計算-費氏數列費氏數列(說明說明)n 費氏數列（Fibonacci）是一序列的數值，從第3項開始每一項接著的數值都是前兩個數值的和，如下所示：0,1,1,2,

32、3,5,8,13,21,34.n 上述費氏數列的第1項為F0，可以得到F0=0，F1=1和F2=F0+F1=1，依序類推，其公式如下所示：Fn=Fn-1+Fn-2，n21-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=%dn,n,n);/*顯示項目*/08:else 09:fn2=0;/*設定 F(n-2)*/

33、10:fn1=1;/*設定 F(n-1)*/11:for(i=2;i 1：在執行函數第6列的if判斷後，頻率計數是1，然後執行第910列後，目前的頻率計數和為3，接著執行第1114列的for迴圈，第11列執行n次（for迴圈共執行n-1次，再加上最後一次比較跳出for迴圈），第1214列執行3*(n-1)=3n-3次，目前是4n，最後第16列可以計算出頻率計數是4n+1。1-6-3 遞迴函數的頻率計數遞迴函數的頻率計數-函數函數n 遞迴函數的頻率計數因為函數會呼叫自己本身，其頻率計數類似迴圈敘述，例如：第1-5-2節階層函數的factorial()遞迴函數，如下所示：01:long facto

34、rial(int n)02:if(n=1)/*終止條件*/03:return 1;04:else05:return n*factorial(n-1);06:1-6-3 遞迴函數的頻率計數遞迴函數的頻率計數-頻率計數頻率計數n 頻率計數的計算，如下所示：第第2列：列：函數本身呼叫遞迴函數共n-1次，所以執行n-1次的比較，再加上主程式呼叫遞迴函數時的第1次比較，一共執行n-1+1次，所以頻率計數是n。第第3列：列：函數只有在最後一次遞迴呼叫才執行，所以頻率計數是1。第第5列：列：函數本身遞迴呼叫共n-1次，所以頻率計數是n-1。n 遞迴函數factorial()總共的頻率計數是n+1+n-1=2

35、n。1-7 Big Oh函數函數n 1-7-1 Big Oh函數的基礎n 1-7-2 Big Oh函數的等級1-7-1 Big Oh函數的基礎函數的基礎-說明說明n 函數O()代表參數頻率計數多項式的級數，唸成Big Oh。O(1)表示頻率計數是常數，O(n)表示頻率計數是an+b，O(n2)表示頻率計數是an2+bn+c，a、b和c是常數，O()函數不計頻率計數的常數，只取其最高次方的項目，所以是O(1)、O(n)和O(n2)。n 例如：費氏數列fibonacci()函數頻率計數的O()函數，如下所示：n=0或1：2O(1)n1：4n+1O(n)n 上述頻率計數4n+1是O(n)，因為當n很

36、大時，係數4和1可以不用考慮，O(n)表示程式執行的頻率計數和n成正比。1-7-1 Big Oh函數的基礎函數的基礎-O(1)O(1)：單行程式碼a=a+1;n 上述程式碼a=a+1是一列單行程式碼，不包含在任何迴圈中，頻率計數是1所以是O(1)。1-7-1 Big Oh函數的基礎函數的基礎-O(n)O(n)：線性迴圈a=0;for(i=0;i 0;i=i/2)a=a+1;n 或a=0;for(i=0;i n;i=i*2)a=a+1;n 上述兩個迴圈的增量是除以2或乘以2，以除來說，如果n=16，迴圈依序為8、4、2、1，其執行次數是對數Log n，其頻率計數是Log n+1，包含最後1次的比

37、較，不計常數所以是O(Log n)。1-7-1 Big Oh函數的基礎函數的基礎-O(nLog n)O(n Log n)：巢狀迴圈擁有內層非線性迴圈a=0;for(i=0;i 0;j=j/2)a=a+1;n 上述巢狀迴圈的外層是線性迴圈的O(n)，內層是非線性迴圈的O(Log n)，所以是：O(n)*O(Log n)=O(n Log n)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;n 上述巢狀迴圈的外層是線性迴圈的O(n)，內層線性迴圈的O(n)，所以是：O(n)*O(n)=O(n2

38、)1-7-2 Big Oh函數的等級函數的等級-說明說明n 程式執行效率的時間複雜度可以使用O(1)、O(Log n)、O(n)、O(n Log n)、O(n2)、O(n3)和O(2n)的Big Oh函數來表示，如下表所示：1-7-2 Big Oh函數的等級函數的等級-成長曲線圖成長曲線圖1-7-2 Big Oh函數的等級函數的等級-比較比較n 如果一個問題有兩種不同演算法，第一種方法的頻率計數是5n，第二種方法的頻率計數是n2/2，我們可以計算頻率計數與n值的關係，如下表所示：1-7-2 Big Oh函數的等級函數的等級-比較說明比較說明n 當n 10時，第一種方法反而比較有效率，函數O()分別為O(n)和O(n2)。n 所以，當n足夠大時，頻率計數的常數就可忽略不計，只需比較其級數，所以O(n)執行效率比O(n2)好。如果n很小時，常數才需要加以考量，如此才能真正比較程式執行效率的優劣。