电脑的基本操作课件.ppt

《电脑的基本操作课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter1演算法分析1.1演算法1.2Big-O演算法分析演算法是解決一問題的有限步驟，而評斷演算法的優劣可利用Big-O分析之，如O(n)比O(n2)來得佳。21.1演算法演算法（Algorithms）是一解決問題（problems）的有限步驟程序。舉例來說，現有一問題為：判斷數字x是否在一已排序好的數字串列s中，其演算法為：從s串列的第一個元素開始，依序的比較，直到x被發現或s串列已達盡頭。假使x被找到，則印出Yes；否則，印出No。31.1演算法當問題很複雜時，上述敘述性的演算法就難以表達出來。因此，演算法大都以類似的程式語言表達之，繼而利用您所熟悉的程式語言執行之。

2、41.1演算法“他的程式寫得比我好嗎？”應該利用客觀的方法進行比較，而此客觀的方法就是複雜度分析（complexityanalysis）。首先必須求出程式中每一敘述的執行次數（其中｛和｝不加以計算），將這些執行次數加總起來。然後求出其Big-O。51.1演算法陣列元素相加（Addarraymembers）61.1演算法矩陣相乘（MatrixMultiplication）71.1演算法81.1演算法循序搜尋（Sequentialsearch）91.1演算法二元搜尋（Binarysearch）101.1演算法費氏數列（遞迴的片段程式）111.1演算法費氏數列（非遞迴的片段程式）121.

3、2Big-O如何去計算演算法所需要的執行時間呢？在程式或演算法中，每一敘述（statement）的執行時間為：此敘述執行的次數，每一次執行所需的時間，兩者相乘即為此敘述的執行時間。由於每一敘述所須的時間必需實際考慮到機器和編譯器的功能，因此通常只考慮執行的次數而已。131.2Big-O下列有三個片段程式，請計算x=x+1的執行次數：141.2Big-O在分析演算法時，一般稱敘述的執行次數為orderofmagnitude，所以上述的(a)、(b)、(c)中，x=x+1的orderofmagnitude分別為1，n，n2。而整個演算法的orderofmagnitude為演算法中每一敘

4、述的執行次數之和。151.2Big-O算完程式敘述的執行次數後，通常利用Big-O來表示此演算法執行的時間。161.2Big-O請看下列範例：3n+2=O(n)，∵我們可找到c=4，n0=2，使得3n+2<4n10n2+5n+1=O(n2)，∵我們可以找到c=11，n0=6，使得10n2+5n+1<11n27*2n+n2+n=O(2n)，∵我們可以找到c=8，n0=4，使得7*2n+n2+n<8*2n10n2+5n+1=O(n3)，原來10n2+5n+1O(n2)，而n3又大於n2，理所當然10n2+5n+1=O(n3)是沒問題的。171.2Big-O其實，我們可以加以證明，當f(

5、n)=amnm+...+a1n+a0時，f(n)=O(nm)181.2Big-O循序搜尋（sequentialsearch）的情形可分，其平均搜尋到的次數為191.2Big-O二元搜尋法乃是資料已經皆排序好，因此由中間（mid）開始比較，便可知欲搜尋的資料（key）落在mid的左邊還是右邊，再將左邊的中間拿出來與key相比，只是每次要調整每個段落的起始位址或最終位址。201.2Big-O211.2Big-O搜尋的次數為log32+1=6，此處的log表示log2。資料量為128個時，其搜尋的次數為log128+1，因此當資料量為n時，其執行的次數為logn+1。221.2Big-O

6、讀者大略可知二元搜尋比循序搜尋好得太多了，其執行敘率為O(logn)。費氏數列（Fibonaccinumber），其定義如下：231.2Big-O241.2Big-O251.2Big-O261.2Big-O當n=3(f3)從上圖可知需計算的項目為5；n=5時，需計算的項目數為15個。因此我們可以下列公式表示：271.2Big-O281.2Big-O上述費氏數列是以遞迴的方式算出，其Big-O為O(2n/2)，若改以非遞迴方式計算的話，其f(n)執行的項目為n+1項。從上表得知，計算費氏數列若採用遞迴方法並不太適合，所以並不是所有的問題皆適合利用遞迴法，有關遞迴的詳細情形，請參閱第五

7、章。291.2Big-OBig-O的圖形表示如下：301.2Big-O例如有一程式的執行次數為n2+10n，則其Big-O為n2，表示此程式執行的時間最壞的情況下不會超過n2，因為n2+10n≦2n2，當c=2，n≧10時311.2Big-O一般常見的Big-O有下列幾種情形：O(1)稱為常數時間（constant）O(logn)稱為次線性時間（sub-linear）O(n)稱為線性時間（linear）O(nlogn)稱為nlognnO(n2)稱為平方時間（quadr