算法合集之《論對(duì)題目中算法的選擇》.ppt

1、論對(duì)算法的選擇,上海市復(fù)旦附中 張?jiān)屏?一、引言,計(jì)算機(jī)競(jìng)賽是一項(xiàng)對(duì)選手計(jì)算機(jī)知識(shí)、編程能力的綜合測(cè)試，在平時(shí)的訓(xùn)練之中，我們一般都會(huì)精益求精，設(shè)法想出最好的算法，但是在競(jìng)賽的時(shí)候，時(shí)間和心理狀態(tài)都是不一樣的，如何在競(jìng)賽中編出能得分盡量多的程序，對(duì)各種算法的靈活運(yùn)用是很重要的。,二、算法的復(fù)雜度,我在這里所說(shuō)的復(fù)雜度，包括編程復(fù)雜度，時(shí)間復(fù)雜度，空間復(fù)雜度，因?yàn)樵诟?jìng)賽幾個(gè)小時(shí)的時(shí)間里，編程復(fù)雜度就不容忽視，知道算法但是程序沒(méi)完成，這是最不理想的情況，對(duì)源程序的最基本的質(zhì)量要求是正確性和可靠性，只要保證在這兩點(diǎn)的情況下，各種算法都是好算法。所以在這三個(gè)復(fù)雜度都考慮的情況下，找到最適宜的算法是必要

2、的。,三、對(duì)于一些題目的思路,在我們做題的時(shí)候，我們先想出的算法不一定是最好的算法，但不是說(shuō)明它是不好的算法，所以，在我們想出一種算法的時(shí)候，要考慮一下它的可行性，如果可行的話，不如自己先把該算法編一編，可以鍛煉自己編那些非標(biāo)準(zhǔn)算法的能力，這樣對(duì)自己面對(duì)新穎題型的時(shí)候是會(huì)有好處的。,例1,問(wèn)題描述 輸入： 一個(gè)正整數(shù)n，以及整數(shù)數(shù)列A1, A2 ,A3 ,An。 一個(gè)正整數(shù)m，以及整數(shù)數(shù)列B1,B2 ,B3,Bm。 其中 （1=n=106, 1=Ai=106，1=m=1000,1=Bi=106） 輸出： 一共m行，每行一個(gè)整數(shù)，第i行所輸出的數(shù)表示數(shù)列A中小于等于Bi的數(shù)的數(shù)目。,例1,算法分

3、析 首先，我們便注意到了n與m的范圍的差距。 本算法運(yùn)用了兩個(gè)數(shù)組 L1.1000000 (記錄數(shù)列A中取值為k的數(shù)有Lk個(gè)) V1.1000 (記錄數(shù)列A中取值在(k-1)*1000+1，k*1000的數(shù)有Vk個(gè)),例1,算法分析 程序流程 ： 預(yù)處理：對(duì)數(shù)組于L，V進(jìn)行清零。 讀入n，依次讀入Ai。對(duì)于每個(gè)Ai， 得出k（k為整數(shù)），使Ai在區(qū)間(k-1)*1000+1，k*1000內(nèi) LAi+,Vk+ 讀入m，依次讀入Bi。對(duì)每個(gè)Bi， 得出k（k為整數(shù)），使Bi在區(qū)間(k-1)*1000+1，k*1000內(nèi) 設(shè)A中小于Bi的數(shù)有S個(gè)，易知 S = 輸出S,例1,復(fù)雜度分析 本算法 計(jì)算

4、每個(gè)S的值最多需要運(yùn)算操作1000+1000=2000次。 每次將一個(gè)Ai記錄的操作需要2次 線段樹(shù) 計(jì)算每個(gè)S的值最多需要運(yùn)算操作(n+m)*log2G 每次將一個(gè)Ai記錄的操作需要(n+m)*log2G 兩種算法的復(fù)雜度比較 其中線段數(shù)對(duì)于計(jì)算S的值與記錄一個(gè)Ai 都只要在 (n+m)*log2G 的運(yùn)算次數(shù)下完成 線段樹(shù)本算法（最壞情況） (n+m)*log2G n*2+m*2000（其中G=106）,例2、營(yíng)業(yè)額統(tǒng)計(jì),問(wèn)題描述 公司的賬本上記錄了公司成立以來(lái)每天的營(yíng)業(yè)額。分析營(yíng)業(yè)情況是項(xiàng)相當(dāng)復(fù)雜的工作，營(yíng)業(yè)額會(huì)出現(xiàn)一定的波動(dòng)，當(dāng)然一定的波動(dòng)是能夠接受的，但營(yíng)業(yè)額突變得很高或是很低，這就

5、證明公司此時(shí)的經(jīng)營(yíng)狀況出現(xiàn)了問(wèn)題。經(jīng)濟(jì)管理學(xué)上定義了一種最小波動(dòng)值來(lái)衡量這種情況： 該天的最小波動(dòng)值 當(dāng)最小波動(dòng)值越大時(shí)，就說(shuō)明營(yíng)業(yè)情況越不穩(wěn)定。 而分析整個(gè)公司的從成立到現(xiàn)在營(yíng)業(yè)情況是否穩(wěn)定，只需要把每一天的最小波動(dòng)值加起來(lái)就可以了。本程序任務(wù)就是編寫(xiě)一個(gè)程序來(lái)計(jì)算這一個(gè)值。第一天的最小波動(dòng)值為第一天的營(yíng)業(yè)額。,例2、營(yíng)業(yè)額統(tǒng)計(jì),問(wèn)題描述 輸入和輸出： 輸入： 輸入文件第一行為正整數(shù)，表示該公司從成立一直到現(xiàn)在的天數(shù)，接下來(lái)的n行每行有一個(gè)正整數(shù) ，表示第i天公司的營(yíng)業(yè)額。 輸出： 輸出文件僅有一個(gè)正整數(shù)，即 ,它小于231。 輸入輸出樣例：,例2、營(yíng)業(yè)額統(tǒng)計(jì),算法分析 本題題意明了，關(guān)鍵是

6、讀入一個(gè)數(shù)，找到前面已經(jīng)輸入的與該數(shù)數(shù)相差最小的數(shù)。 本算法運(yùn)用了兩個(gè)數(shù)組 L1.32767 V1.327 其中的定義與例1中的一樣，只不過(guò)是對(duì)數(shù)的下標(biāo)進(jìn)行處理。,例2、營(yíng)業(yè)額統(tǒng)計(jì),算法分析 預(yù)處理： 把全部數(shù)據(jù)讀入，將A從小到大排序，這樣得到一個(gè)序列B1,B2,Bn。 累加器S賦值為0 主過(guò)程： 讀入將要處理的數(shù)據(jù)，對(duì)每天的營(yíng)業(yè)額進(jìn)行處理，求出該天的最小波動(dòng)值。 結(jié)尾階段：輸出S,主過(guò)程 讀入當(dāng)天的營(yíng)業(yè)額P。 用二分查找法在數(shù)列B中找到Bq=P 然后利用數(shù)組L，V，設(shè)法找到已經(jīng)儲(chǔ)存的下標(biāo)之中小于等于q中最大的下標(biāo)ga，與大于等于q中最小的下標(biāo)gb， 且Lga0，Lgb0，然后通過(guò)ga與gb計(jì)算出當(dāng)前的最小波動(dòng)值。 將計(jì)算出的最小波動(dòng)值加入累加器S,例2、營(yíng)業(yè)額統(tǒng)計(jì),例2、營(yíng)業(yè)額統(tǒng)計(jì),復(fù)雜度分析 預(yù)處理的排序時(shí)間復(fù)雜度Nlog2N 對(duì)于計(jì)算每天的最小波動(dòng)值。大約需要32767*500的運(yùn)算次數(shù)。 總計(jì)時(shí)間復(fù)雜度為O(n1.5)左右，可以在規(guī)定時(shí)間之內(nèi)完成。 而平衡樹(shù)的時(shí)間復(fù)雜度為O(nlog2n)，比較之下顯然平衡樹(shù)的時(shí)間復(fù)雜度小于本算法的時(shí)間復(fù)雜度。但本算法的測(cè)試與修改卻比平衡樹(shù)容易的多，因?yàn)樗欠侄嗖竭M(jìn)行，可以分步進(jìn)行測(cè)試而且每步的要求技術(shù)都不高。,四、總結(jié),每個(gè)算法都是有它自己的優(yōu)勢(shì)，每種算法的效果在不同的場(chǎng)合是不一樣的，在