數(shù)據(jù)結(jié)構(gòu)常見問題：12單元4 算法及描述

1、數(shù)據(jù)結(jié)構(gòu)課程常見問題 -單元3 算法及描述1算法及描述解析：算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。常見的算法有：窮舉法，分治法，篩選法，構(gòu)造法，貪心法，動(dòng)態(tài)規(guī)劃等。一般說來，算法可以用自然語言、流程圖和程序來描述。下面通過一個(gè)具體的例子來說明算法的描述方法。例1、H數(shù)問題（Hnum）問題描述所謂數(shù)，是指該數(shù)除以外最多只有2，3，5，7四種因子，如630即為數(shù)，而22不是。要求對(duì)鍵盤輸入的自然數(shù)，求出第個(gè)數(shù)。如=30，應(yīng)輸出49。規(guī)定要求的數(shù)不超出長整型數(shù)的范圍。算法分析從數(shù)的定義可以看出，如果一個(gè)數(shù)是數(shù)，那么將它的2，3，5，7四種因子去掉以

2、后必然是剩下1。下面就根據(jù)數(shù)的這一特性用窮舉法來解決這個(gè)問題。首先用自然語言描述該算法。算法1_1：窮舉法計(jì)算第n個(gè)H數(shù)第一步：從鍵盤輸入一個(gè)自然數(shù)給N；第二步：將h置為1，order置為1； 表示第一個(gè)數(shù)為1第三步：如果order=n ，則轉(zhuǎn)第七步；否則轉(zhuǎn)第四步；第四步：h增加1，并將k的值置為h；第五步：將k中的2，3，5，7四種因子去掉；第六步：如果k=1，則order 增加1；第七步：輸出h；以上描述中第五步的描述不夠明確，下面對(duì)去掉k中因子i作更進(jìn)一步的說明:第1步：如果k是i的倍數(shù)，則轉(zhuǎn)第2步，否則算法結(jié)束；第2步：將k置為k/i；第3步：轉(zhuǎn)第1步；有了上述用自然語言描述的算法后，

3、就很容易編寫出求解數(shù)問題的程序（Hnum1.pas），借助計(jì)算機(jī)來計(jì)算結(jié)果了。程序中將2，3，5，7存放在數(shù)組mark中。參考程序1program Hnum1(input，output);const mark:array 1.4 of integer=(2，3，5，7);var i，h，k，n，order:longint;begin write(Input n:); readln(n); h:=1; order:=1; while order2000時(shí)，更是無法滿足競賽的時(shí)間要求（一般每個(gè)測試點(diǎn)的時(shí)限為1秒）。后面將討論這一問題的更高效的算法。2算法的特性解析：算法是求解問題的步驟或規(guī)則的描述

4、，至于用什么工具實(shí)現(xiàn)或由誰去執(zhí)行，算法描述中并沒有規(guī)定。現(xiàn)代算法通常是作為編程的依據(jù)而言的。一個(gè)算法雖然與用什么語言去遍程、在什么計(jì)算機(jī)上運(yùn)行沒有必然的關(guān)聯(lián)，但作為算法設(shè)計(jì)者來說，對(duì)于算法的一些重要特性是應(yīng)該掌握的。一個(gè)算法應(yīng)該具有下列特性： 有窮性：一個(gè)算法必須總是(對(duì)任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。 確定性：算法的每一步，必須是確切地定義的，讀者理解時(shí)不會(huì)產(chǎn)生二義性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。 輸入：一個(gè)算法有0個(gè)或多個(gè)輸入。它們是在算法開始前對(duì)算法給定的量，這些輸入取自于特定對(duì)象的集合。 輸出

5、：一個(gè)算法有一個(gè)或多個(gè)輸出。它們是同輸入有某種特定關(guān)系的量。 可行性：算法應(yīng)該是可行的。這意味著算法中所有有待實(shí)現(xiàn)的運(yùn)算都是相當(dāng)基本的，也就是說，它們?cè)瓌t上都是能夠精確地進(jìn)行的，甚至人們僅用筆和紙做有窮次運(yùn)算即可完成。3算法的評(píng)價(jià)解析：對(duì)于解決同一個(gè)問題，往往能夠設(shè)計(jì)出許多不同的算法。例如，對(duì)于數(shù)據(jù)的排序問題，我們可以用選擇排序、冒泡排序、插入排序、快速排序、希爾排序等多種算法，對(duì)于這些排序算法，他們各有優(yōu)缺點(diǎn)，其算法性能如何有待用戶的評(píng)價(jià)。因此，對(duì)問題求解的算法優(yōu)劣的評(píng)定稱為“算法評(píng)價(jià)”。算法評(píng)價(jià)的目的，在于從解決同一問題的不同算法中選擇出較為合適的一種算法，或者是對(duì)原有的算法進(jìn)行改造、加工

6、，使其更優(yōu)、更好。一般對(duì)算法進(jìn)行評(píng)價(jià)主要有四個(gè)方面：（1）算法的正確性正確性是設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的首要條件，如果一個(gè)算法不正確，其它方面就無從談起。一個(gè)正確的算法是指在合理的輸入數(shù)據(jù)下，能在有限的運(yùn)行時(shí)間內(nèi)得到正確的結(jié)果。通過對(duì)數(shù)據(jù)輸入的所有可能情況的分析和上機(jī)調(diào)試，以證明算法是否正確。（2）算法的簡單性算法簡單有利于閱讀，也使得證明算法正確性比較容易，同時(shí)有利于程序的編寫、修改和調(diào)試。但是算法簡單往往并不是最有效。因此，對(duì)于問題的求解，我們往往更注意有效性。有效性比簡單性更重要。（3）算法的運(yùn)行時(shí)間：時(shí)間復(fù)雜性算法的運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間。它大致等于計(jì)算機(jī)執(zhí)行簡單操作

7、（如賦值操作，比較操作等）所需要的時(shí)間與算法中進(jìn)行簡單操作次數(shù)的乘積。通常把算法中包含簡單操作次數(shù)的多少叫做“算法的時(shí)間復(fù)雜性”。它是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度，一般用數(shù)量級(jí)的形式給出。度量一個(gè)程序的執(zhí)行時(shí)間通常有以下兩種方法：一種是“事后統(tǒng)計(jì)”的方法。因?yàn)楹芏嘤?jì)算機(jī)內(nèi)部都有計(jì)時(shí)功能，有的甚至可精確到毫秒級(jí)，不同算法的程序可通過一組或若干組相同的統(tǒng)計(jì)數(shù)據(jù)以分辨優(yōu)劣。但這種方法有兩個(gè)缺陷：一是必須先運(yùn)行依據(jù)算法編制的程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。因此人們常常采用另一種“事前分析估算”的方法。 “事前分析估算”的方法基于：一個(gè)用高級(jí)程序語

8、言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：依據(jù)的算法選用何種策略。不同算法、不同策略所消耗的CPU時(shí)間顯然是不同的； 問題的規(guī)模。例如求100以內(nèi)還是1 000 000以內(nèi)的素?cái)?shù)； 書寫程序的語言。對(duì)于同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低； 編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量：編譯器的區(qū)別、版本會(huì)有所不同； 機(jī)器執(zhí)行指令的速度。顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行時(shí)，效率均不相同。這表明使用絕對(duì)的時(shí)間單位衡量算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴于問題的

9、規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本運(yùn)算的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。例如，在如下所示的兩個(gè)N*N的矩陣相乘的算法中，“乘法”運(yùn)算是“矩陣相乘問題”的基本操作。整個(gè)算法的執(zhí)行時(shí)間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù)n3 成正比，記作T（n）=O（n3）。 for i:=1 to n do for j:=1 to n do begin c

10、i，j:= 0; for k:=1 to n do ci，j:= ci，j+ai，k * bk，j end;一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間量度記作：T（n）= O（f（n）它表示問題規(guī)模n的增大、算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。顯然，被稱作問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)，例如：在下列三個(gè)程序段中，x:=x+1for i:=1 to

11、n do x:=x+1;for j:=1 to n do for k:=1 to n do x:=x+1含基本操作“x增1”的語句x:=x+1的頻度分別為1，n和 n2 ，則這三個(gè)程序段的時(shí)間復(fù)雜度分別為O（1），O（n），O（n2），分別稱為常量階、線性階和平方階。算法還可能呈現(xiàn)的時(shí)間復(fù)雜度有：對(duì)數(shù)階O（log n），指數(shù)階O（2n）等。在n很大時(shí)， 不同數(shù)量級(jí)時(shí)間復(fù)雜度顯然有O（1）O（log n）O（n）O（nlog n）O（n2） O（n3）O（2n），可以看出，在算法設(shè)計(jì)時(shí)，我們應(yīng)該盡可能選用多項(xiàng)式階O(nk )的算法，而不希望用指數(shù)階的算法。一般情況下，對(duì)一個(gè)問題(或一類算法)只需

12、選擇一種基本操作來討論算法的時(shí)間復(fù)雜度即可，有時(shí)也需要同時(shí)考慮幾種基本操作，甚至可以對(duì)不同的操作賦以不同權(quán)值，以反映執(zhí)行不同操作所需的相對(duì)時(shí)間，這種做法便于綜合比較解決同一問題的兩種完全不同的算法。由于算法的時(shí)間復(fù)雜度考慮的只是對(duì)于問題規(guī)模n的增長率，則在難以計(jì)算基本操作執(zhí)行次數(shù)(或語句頻度)的情況下，只需求出它關(guān)于n的增長率或階即可，一般可忽略常數(shù)項(xiàng)、底階項(xiàng)、甚至系數(shù)。 例如，在下列程序段中:for i:=2 to n do for j:=2 to i-1 do x:=x+1語句x:=x+1執(zhí)行次數(shù)關(guān)于n的增長率為n2 ，它是語句頻度表達(dá)式(n-1)(n-2)/2中增長最快的一項(xiàng)。4、算法所

13、占用的存儲(chǔ)空間：空間復(fù)雜性算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間的大小被定義為“算法的空間復(fù)雜性”?？臻g復(fù)雜性包括程序中的變量、過程或函數(shù)中的局部變量等所占用的存儲(chǔ)空間以及系統(tǒng)為了實(shí)現(xiàn)遞歸所使用的堆棧兩部分。算法的空間復(fù)雜性一般也以數(shù)量級(jí)的形式給出。類似于算法的時(shí)間復(fù)雜度，以空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作S(n)=O(f(n)其中n為問題的規(guī)模(或大小)。一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的額外

14、空間，否則應(yīng)同時(shí)考慮輸入本身所需空間(和輸入數(shù)據(jù)的表示形式有關(guān))。若額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。如果所占空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來分析，即以所占空間可能達(dá)到的最大值作為其空間復(fù)雜度。5、時(shí)間和空間復(fù)雜性的計(jì)算和討論下面我們通過一個(gè)實(shí)例，了解算法的時(shí)間復(fù)雜性和空間復(fù)雜性的計(jì)算方法。例2、計(jì)算y=anxn+an-1xn-1+an-2xn-2+a1x+a0的值。問題分析該問題計(jì)算的規(guī)模在于n的大小，n越大計(jì)算量也越大，乘積和累加的次數(shù)也愈多，這里n就是問題的規(guī)模。對(duì)于該問題的求解的基本條件是：已知x的值和系數(shù)a0an。（與問題規(guī)模n有關(guān)，空間

15、的單元是固定的，若相差幾個(gè)單元，可以忽略不計(jì)）算法2_1：y=a0 ;for k:=1 to n do begin s:=ak ; for j:=1 to k do s:=s*x y:=y+s ; end ;writeln ( y=， y ) ;在該運(yùn)算中所需存儲(chǔ)單元a0，a1， ，an ，以及固定的幾個(gè)簡單變量，所以其空間復(fù)雜性與規(guī)模n成正比，即為O（n）。而時(shí)間復(fù)雜性是內(nèi)循環(huán)乘法計(jì)算和外循環(huán)的累加計(jì)算，計(jì)算y共用乘法次數(shù)是：1+2+3+n=n(n+1)/2， 加法僅n次，而在計(jì)算機(jī)內(nèi)部實(shí)現(xiàn)乘法要比加法花費(fèi)更多的時(shí)間，所以該算法的時(shí)間復(fù)雜性為O（n(n+1)/2）O（n*n/2）O（n2）。算法2_2：算法2_1中的乘法運(yùn)算有重復(fù)計(jì)算：xk不需要每次從1，x， x2，x3， ， xk乘法去實(shí)現(xiàn)，只要在原先xk-1基礎(chǔ)上再做一次乘法就可以得到xk 的結(jié)果，多用一個(gè)b數(shù)組存放1，x， x2，x3， ， xn，該問題的空間復(fù)雜性為O（2n）O(n)。b0:=1 ;for k:=1 to n do bk:= nk-1 *x ;y:=a0 ;for k:=1 to n do y:=y+ak*bk ;writeln(y=，y);此算法用了兩次單循環(huán)命令，共用了2n次乘法和n次加法，時(shí)間復(fù)雜性為O（2n）O(n)