算法與算法分析

1、1& 第一章第一章 緒論緒論 1.1 1.1 引言引言 1.2 1.2 算法算法及算法分析（算法評價）及算法分析（算法評價） 2什么是算法？ 算法是對解決問題的方法的一種精確描述。 并非所有問題都有算法，有些問題經(jīng)研究可行，則可能有相應(yīng)算法；而有些問題經(jīng)研究不可行，則沒有相應(yīng)算法。 因此，算法研究在某種意義上就是可行性研究。 3算法的性質(zhì) 算法可以理解為動作序列的有限集合 僅有一個初始動作 每個動作的后繼動作是確定的 算法的終止表示問題得到解答或問題沒有解答 4算法算法是為了解決某類問題而規(guī)定的一個有限長的操作序列操作序列。一個算法必須滿足以下五個重要特性：1 1有窮性有窮性 2 2確

2、定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出算法的性質(zhì)51 1有窮性有窮性 對于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間有限時間內(nèi)完成。 2 2確定性確定性 對于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且并且在任何條件下，算法都只有一在任何條件下，算法都只有一條執(zhí)行路徑。條執(zhí)行路徑。63 3可行性可行性 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。4 4有輸入有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變

3、量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。7 5 5有輸出有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。8算法設(shè)計的原則設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲量需求高效率與低存儲量需求91 1正確性正確性 首先，首先，算法應(yīng)當(dāng)滿足滿足以特定的“規(guī)格規(guī)格說明說明”方式給出的需求需求。 其次，其次，對算法是否“正確正確”的的理解可以有以下四個層次四個層次：a a程序中不含語法錯誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)

4、果；10 c c程序?qū)τ诰倪x擇的、典型、苛刻且程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；要求的結(jié)果；通常以第 c c 層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。 d d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；112. . 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計算機(jī)執(zhí)行，因此算法應(yīng)該易易于于人的理解理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試。123健壯性健壯性 當(dāng)輸入的數(shù)據(jù)非法非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并

5、且，處理出處理出錯的方法錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個表示錯誤或錯誤性質(zhì)的值表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。134高效率與低存儲量需求高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模有關(guān)。14& 第一章第一章 緒論緒論 1.1 1.1 引言引言 1.2 1.2 算法及算法及算法分析算法分析（算法評價）（算法評價） 15算法分析與算法復(fù)雜度 算法分析的任務(wù)是對設(shè)計出的每一個具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度，探討具體算法對問題的適應(yīng)性 算法的復(fù)雜度分時間復(fù)雜度和空間復(fù)雜度。 計

6、算機(jī)理論科學(xué)中，按照計算復(fù)雜性研究問題求解的難易性，可把問題分為 p類、np類 和 np-完全類。 16算法的效率對于一個問題通常有多種解法（算法），應(yīng)該選擇哪一種呢？計算機(jī)程序設(shè)計的核心有兩個目標(biāo)（有時它們互相沖突）1. 設(shè)計一種容易理解、編碼和調(diào)試的算法2. 設(shè)計一種能有效利用計算機(jī)資源的算法17算法的效率 (cont)目標(biāo)1涉及到軟件工程原理目標(biāo)2涉及到數(shù)據(jù)結(jié)構(gòu)與算法分析本課程主要講的是與目標(biāo)2有關(guān)的問題怎樣度量算法的代價、效率呢？18如何度量效率?1. 實驗比較（運行程序）2. 漸近算法分析asymptotic algorithm analysis關(guān)鍵資源:影響運行時間的因素:對很多算

7、法而言，運行時間依賴與輸入的規(guī)模執(zhí)行算法所需要的時間t寫成輸入規(guī)模n的函數(shù)，記為t(n)19怎樣比較兩種算法解決問題的效率呢？ 實驗比較 用源程序分別實現(xiàn)這兩種算法，然后輸入適當(dāng)?shù)臄?shù)據(jù)運行，測算兩個程序各自的開銷 這是一種事后統(tǒng)計的方法 漸近算法分析(asymptotic algorithm analysis)，簡稱算法分析(algorithm analysis) 可以估算出當(dāng)問題規(guī)模變大時，一種算法及實現(xiàn)它的程序的效率和開銷 這是一種事前分析估算的方法20“規(guī)模”與“基本操作” 判斷算法性能的一個基本考慮是處理一定“規(guī)?！?(size)的輸入時該算法所需執(zhí)行的“基本操作” (basic op

8、eration)數(shù) “規(guī)?！币话闶侵篙斎肓康臄?shù)目 比如，在排序問題中，問題的規(guī)?？梢杂帽慌判蛟氐膫€數(shù)來衡量21“規(guī)?！迸c“基本操作”（續(xù)） 一個“基本操作”必須具有這樣的性質(zhì)：完成該操作所需時間與操作數(shù)的具體取值無關(guān) 在大多數(shù)高級語言中，下列操作是基本操作： 賦值運算 簡單算術(shù)運算 簡單布爾運算 簡單io操作 函數(shù)返回 n個整數(shù)累加不是基本操作 因為其代價依賴于n的值(即大小)22運行時間和增長率 由于影響運行時間的最主要因素一般是輸入的規(guī)模，所以經(jīng)常把執(zhí)行算法所需要的時間t寫成輸入規(guī)模n的函數(shù)，記為t(n)我們總是假設(shè)t(n)為非負(fù)值 算法的增長率(growth rate)是指當(dāng)輸入規(guī)模增

9、長時，算法代價的增長速率23最佳、最差和平均情況不是相同規(guī)模的所有輸入的運行時間都相同順序搜索法（sequential search）從一個n元一維數(shù)組中找出一個給定的值k :從第一個元素開始，依次檢索每一個元素，直到找到k為止最佳情況:最差情況:平均情況:24請用通俗的例子談?wù)剬υ鲩L率和平均情況 兩個概念的理解請郵件告訴我（）25growth rate graph265.1.1 時間復(fù)雜性（續(xù)）時間復(fù)雜性（續(xù)） 更快的計算機(jī)，還是更快的算法?27時間復(fù)雜度對解題速度的影響o(n)解解 題題 速速 度度n = 10n = 30n = 60n0.01 ms0.03 ms0.06 msn20.1

10、ms0.9 ms3.6 msn50.1 s24.3 s13.0 min2n1.0 ms17.9 min366.0 世紀(jì)世紀(jì)3n0.059 s6.5 年年1.31013 世世紀(jì)紀(jì)28u 阿達(dá)爾定律設(shè) f 為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比，p 處理機(jī)的數(shù)目，sp 為并行計算機(jī)系統(tǒng)最大的加速能力（單位：倍），則設(shè) f =1%，p ，則sp =100。串行計算與并行計算pffsp1129算法分析的任務(wù)是對設(shè)計出的每一個具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度，探討具體算法對問題的適應(yīng)性 算法的時間復(fù)雜度 規(guī)模 基本操作 增長率 平均情況 效率請把下列的術(shù)語融入到上句中，請把

11、下列的術(shù)語融入到上句中，對算法分析的任務(wù)進(jìn)行更加清晰的說明對算法分析的任務(wù)進(jìn)行更加清晰的說明30漸近分析:大o定義: 對于非負(fù)函數(shù)t(n)，若存在兩個正常數(shù)c和n0，使得當(dāng)nn0時有t(n)cf(n)， 則稱t(n)在集合o(f(n)中。用法: 這個算法最佳、平均、最差情況（下的增長率的上限）在o(n2)中.含意: 對于問題的所有最佳、平均、最差情況輸入，只要輸入規(guī)模足夠大(即 nn0), 該算法總能在cf(n) 步以內(nèi)完成.31上限:大o (cont)增長率的上限用符號o表示，稱為大o表示法(big-oh notation).example: if t(n) = 3n2 then t(n)

12、is in o(n2).希望最“緊”（即最?。┑纳舷?雖然 t(n) = 3n2 可以說它在o(n3)中, 我們更喜歡用o(n2).32上限的例子例1:考慮找出整數(shù)數(shù)組中某個元素的順序檢索法 (average cost).如果訪問并檢查數(shù)組中的一個元素需要時間cs (cs為常數(shù))，那么在平均情況下t(n) = csn/2 。當(dāng)n 1時，csn/2 1，c1n2 + c2n = c1n2 + c2n2 = (c1 + c2)n2.因此取c = c1 + c2 and n0 = 1，有t(n) n0 時有t(n) = cg(n) ，則稱t(n) 在集合(g(n)中意義: 對于問題的所有最佳、平均、

13、最差情況輸入，只要輸入規(guī)模足夠大(即 nn0),該算法的完成至少需要cf(n)步.下限.35big-omega example例1：假定t(n) = c1n2 + c2n. (c1，c20)則有 c1n2 + c2n = c1n2 for all n 1.因此，取c = c1 ，n0 = 1 ，有t(n) = cn2.所以,根據(jù)定義, t(n) 在(n2)中 也可以說t(n)在 (n)中我們希望找到一個最“緊”的可能限制.（最大下限）36theta notation上限和下限描述了算法運行時間的范圍當(dāng)上、下限相等時，可以用表示法定義: 如果非負(fù)函數(shù)t(n)既在o(h(n)中，又在(h(n)中，

14、則稱算法t(n)是(h(n)。這時也說t(n)與h(n)同階37a common misunderstanding“算法最佳情況是輸入規(guī)模為1時，因為這時運行最快”。錯誤！大o指的是當(dāng)n趨近于時的增長率最佳情況指的是在規(guī)模為n的所有輸入中哪個輸入運行最快。38a common misunderstanding混淆了最差情況和上限上限指的是增長率最差情況指的是給定規(guī)模的所有可能輸入中最差的輸入，消耗（運行）的時間最大39simplifying rules1. if f(n) is in o(g(n) and g(n) is in o(h(n), then f(n) is in o(h(n).2.

15、 if f(n) is in o(kg(n) for any constant k 0, then f(n) is in o(g(n).3. if f1(n) is in o(g1(n) and f2(n) is in o(g2(n), then (f1 + f2)(n) is in o(max(g1(n), g2(n).4. if f1(n) is in o(g1(n) and f2(n) is in o(g2(n) then f1(n)f2(n) is in o(g1(n)g2(n).40程序運行時間的計算(1)example 1: a = b;this assignment takes

16、constant time, so it is (1).example 2:sum = 0;for (i=1; i=n; i+) sum += n;時間代價為時間代價為(1)時間代價為時間代價為nincnc1)(41程序運行時間的計算(2)example 3:sum = 0;for (i=1; i=n; i+) for (j=1; j=i; j+) sum+;for (k=0; kn; k+) ak = k;時間代價為常量時間代價為常量c1時間代價為時間代價為c2n時間代價為時間代價為)(2) 1(23111333ncnnciccniijni42程序運行時間的計算(3)example 4:su

17、m1 = 0;for (i=1; i=n; i+) for (j=1; j=n; j+) sum1+;sum2 = 0;for (i=1; i=n; i+) for (j=1; j=i; j+) sum2+;時間代價為時間代價為(n2)時間代價為時間代價為(n2)43程序運行時間的計算(4)example 5:sum1 = 0;for (k=1; k=n; k*=2) for (j=1; j=n; j+) sum1+;sum2 = 0;for (k=1; k=n; k*=2) for (j=1; j=k; j+) sum2+;第一段程序的時間代價為第一段程序的時間代價為 (nlogn)第二段程

18、序的時間代價為第二段程序的時間代價為 (n)外層for循環(huán)當(dāng)i=1, 2, 22, , 2k=n時執(zhí)行, 總共執(zhí)行1+k次，因為k=logn, 所以總共執(zhí)行1+logn次。又內(nèi)層循環(huán)執(zhí)行次數(shù)恒為n，所以第一段程序的總時間代價可表示為n(1+logn), 即(nlogn)外層for循環(huán)當(dāng)i=1, 2, 22, , 2k=n時執(zhí)行, 而內(nèi)層循環(huán)執(zhí)行k次，所以第二段程序的總時間代價可表示為1+2+22+ + 2k= , 由公式2.9可知，其和為2k+1-1, 因為k=logn, 所以總時間代價為2n-1, 即(n)kii0244其他控制語句 while循環(huán)、do-while循環(huán)分析方法與for循環(huán)類

19、似 if語句最差情況時間代價是then和else部分中時間代價較大的那一個對于平均情況代價也是如此假設(shè)n的取值與執(zhí)行哪一條指令的概率無關(guān) switch語句最差情況時間代價是所有分支中開銷最大的一個 子程序調(diào)用加上執(zhí)行子程序的時間45問題的分析 問題代價的上限：已知最優(yōu)算法的代價上限 問題代價的下限：所有可能算法的代價下限（包括尚未設(shè)計出來的算法）46多參數(shù)問題compute the rank ordering for all c pixel values in a picture of p pixels.for (i=0; ic; i+) / initialize count counti =

20、 0;for (i=0; ip; i+) / look at all pixels countvalue(i)+; / increment countsort(count); / sort pixel countsif we use p as the measure, then time is (p log p).more accurate is (p + c log c).47空間代價 與分析時間代價類似與分析時間代價類似 漸近分析中增長率的概念對于空間代價同樣適漸近分析中增長率的概念對于空間代價同樣適用用 時間代價是相對于處理某個數(shù)據(jù)結(jié)構(gòu)的算法而時間代價是相對于處理某個數(shù)據(jù)結(jié)構(gòu)的算法而言的

21、言的 空間代價是相對于該數(shù)據(jù)結(jié)構(gòu)本身而言的空間代價是相對于該數(shù)據(jù)結(jié)構(gòu)本身而言的48空間/時間權(quán)衡原則(space/time tradeoff principle) 以時間換空間以時間換空間 信息壓縮存儲信息壓縮存儲 以空間換時間以空間換時間 查找表查找表 基于磁盤的空間基于磁盤的空間/時間權(quán)衡原則時間權(quán)衡原則 在磁盤上的存儲代價越小，程序運行得越快在磁盤上的存儲代價越小，程序運行得越快49小結(jié) 算法分析的動機(jī)、基本符號和基本技術(shù) 增長率的概念 增長率的上限和下限的概念 能夠區(qū)分一種算法的代價和一個問題的代價50第一部分小結(jié) 數(shù)據(jù)結(jié)構(gòu)和算法 效率 代價和效益 數(shù)據(jù)結(jié)構(gòu)的定義；adt 算法分析 動

22、機(jī)：增長率 基本符號：o、51什么情況下，可以直接用表示算法的復(fù)雜度？即什么情況下，算法的下限和上限相等。 請郵件告訴我（）52習(xí)題講解寫出下列程序段平均情況下時間代價的表示式。假設(shè)所有變量類型都為int：(a)a = b + c;d = a + e;(b)sum = 0;for(i=0;i3;i+)for(j=0;jn;j+)sum+;(c)sum = 0;for(i=0;in*n;i+) sum+;時間代價為時間代價為(1)時間代價為時間代價為(n)時間代價為時間代價為(n2)53(d)假設(shè)數(shù)組a中含有n個元素，函數(shù)random花的時間是常數(shù)值，sort需要執(zhí)行nlogn步。for(i=0;in;i+)for(j=0;jn;j+) ai = random(n);sort(a,n);(e)假設(shè)數(shù)組a中元素為從0到n1的任意一個排列。sum3 = 0;for(i=0;in;i+)for(j=0;aj!=i;j+) sum3+;時間代價為時間代價為(n2logn)時間代價為時間代價為 = (n2)nii154(f)sum = 0;if(even(n)for(i=0;in;i+) sum+;else sum = sum + n;時間代價為時間代價為(