Chapter1演算法分析PPT課件

1、資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 2 演算法（Algorithms）是一解決問(wèn)題（problems）的有限步驟程序。舉例來(lái)說(shuō)，現(xiàn)有一問(wèn)題為：判斷數(shù)字x是否在一已排序好的數(shù)字串列s中，其演算法為：從s串列的第一個(gè)元素開(kāi)始，依序的比較，直到x被發(fā)現(xiàn)或s串列已達(dá)盡頭。假使x被找到，則印出Yes；否則，印出No。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 3當(dāng)問(wèn)題很複雜時(shí)，上述敘述性的演算法就難以表達(dá)出來(lái)。因此，演算法大都以類似的程式語(yǔ)言表達(dá)之，繼而利用您所熟悉的程式語(yǔ)言執(zhí)行之。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 4應(yīng)該利用客觀的方法進(jìn)行比較，而此客觀的方法就是複雜度分析（co

2、mplexity analysis）。首先必須求出程式中每一敘述的執(zhí)行次數(shù)（其中和不加以計(jì)算），將這些執(zhí)行次數(shù)加總起來(lái)。然後求出其Big-O。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 5陣列元素相加（Add array members）資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 6矩陣相加資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 7矩陣相乘（Matrix Multiplication）資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 8資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 9循序搜尋（Sequential search）資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 10如何去計(jì)算

3、演算法所需要的執(zhí)行時(shí)間呢？在程式或演算法中，每一敘述（statement）的執(zhí)行時(shí)間為：n此敘述執(zhí)行的次數(shù)，n每一次執(zhí)行所需的時(shí)間，兩者相乘即為此敘述的執(zhí)行時(shí)間。由於每一敘述所須的時(shí)間必需實(shí)際考慮到機(jī)器和編譯器的功能，因此通常只考慮執(zhí)行的次數(shù)而已。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 11資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 12請(qǐng)看下列範(fàn)例：資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 13其實(shí)，我們可以加以證明，當(dāng)f(n)=amnm +.+a1n+a0 時(shí)，f(n)=O(nm)資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 14Big-O的圖形表示資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使

4、用 C 語(yǔ)言語(yǔ)言 15例如有一程式的執(zhí)行次數(shù)為n2+10n，則其Big-O為n2，表示此程式執(zhí)行的時(shí)間最壞的情況下不會(huì)超過(guò)n2，因?yàn)閚2+10n2n2，當(dāng)c=2，n10時(shí)資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 16一般常見(jiàn)的Big-O有幾種類別：資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 17除Big-O之外，用來(lái)衡量效率的方法還有資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 18除Big-O之外，用來(lái)衡量效率的方法還有資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 19資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 20循序搜尋（sequential search）的情形可分，其平均搜尋

5、到的次數(shù)為資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 21二元搜尋法 乃是資料已經(jīng)皆排序好，因此由中間（mid）開(kāi)始比較，便可知欲搜尋的資料（key）落在mid的左邊還是右邊，再將左邊的中間拿出來(lái)與key相比，只是每次要調(diào)整每個(gè)段落的起始位址或最終位址。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 22資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 23資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 24搜尋的次數(shù)為log32+1=6，此處的log表示log2。資料量為128個(gè)時(shí)，其搜尋的次數(shù)為log128+1，因此當(dāng)資料量為n時(shí)，其執(zhí)行的次數(shù)為logn+1。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 25一個(gè)有趣的例子費(fèi)氏數(shù)列（Fibonacci number），其定義如下：資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 26資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 27資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 28當(dāng)n=3(f3)從上圖可知需計(jì)算的項(xiàng)目為5；n=5時(shí)，需計(jì)算的項(xiàng)目數(shù)為15個(gè)。因