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

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

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

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

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

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

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