論文-減少冗余與算法優(yōu)化

減少冗余算法優(yōu)化 第10頁減少冗余與算法優(yōu)化【摘要】在信息學競賽中，我們經常會遇到冗余，而冗余會造成算法、程序的效率不同程度的降低：有的是微不足道的，而有的會導致算法復雜度大大提高。本文針對后者，舉例說明冗余對算法效率的影響和如何減少冗余。【關鍵字】冗余、算法優(yōu)化【正文】一引言信息學競賽中，我們所追求的目標之一，是使程序用最少的時間解決問題，也就是達到最高的效率。實際生活中也同樣需要這樣，高效率者往往會在競爭中取得優(yōu)勢。冗余，是指多余的或重復的操作。在搜索、遞推、動態(tài)規(guī)劃等諸多的算法中，都會出現(xiàn)冗余。由冗余的定義，要使算法達到最高的效率，必須去除算法中的冗余處理。但完全去除冗余是難以實現(xiàn)的，使程序用絕對最少的時間解決問題也是很難的，通常需要退一步，將目標改為：使程序用盡量少的時間解決問題。由冗余的定義，可以得到：要提高算法的效率，必須減少算法中的冗余處理。要減少冗余，需要在大量的做題過程中，不斷探索，不斷積累經驗。下面就讓我們通過兩個具體的例子來研究冗余是如何影響算法效率的以及如何減少冗余。二整數(shù)拆分2.1問題描述①①題目來源：金愷原創(chuàng)將正整數(shù)N拆分成若干個整數(shù)的和，使拆分成的數(shù)是2的非負整數(shù)冪的形式。問有多少種拆分方案。如果兩個方案僅有數(shù)的順序不同，它們算作同一種方案。如：當N=5時，可以拆分成下面的形式：5=1+1+1+1+15=1+1+1+25=1+2+25=1+4所以，5有4種拆分方案。2.2粗略分析此題可用遞推解決(為什么？請讀者自己思考^_^)：用表示i拆分成若干個數(shù)，其中最大的數(shù)不超過的拆分總數(shù)。則：，即i拆分成若干個數(shù)，其中最大的數(shù)不超過的拆分方案只有一種：把i拆分成i個1。當i>0,j>0時，由兩類組成：

第一類：拆分成的最大數(shù)正好是，其總數(shù)為；

第二類：拆分成的最大數(shù)小于，其總數(shù)為。所以。最后要計算的目標是F[N,M]。因為必須，所以，又有。不難得出：總的時間復雜度是此處所講的時空復雜度都忽略了高精度的因素。因為當N達到10000000時答案也只有60位，這個數(shù)字是比較小的。，空間復雜度也是?？瓷先?，這個復雜度已經很低了。但是，復雜度能不能再低一點兒呢？此處所講的時空復雜度都忽略了高精度的因素。因為當N達到10000000時答案也只有60位，這個數(shù)字是比較小的。2.3減少冗余為了便于研究，可以首先處理N是2的整數(shù)冪這種特殊情況，然后把N不是2的整數(shù)冪的情況化為N是2的整數(shù)冪的情況處理。2.3.1當N是2的整數(shù)次設(M為非負整數(shù))。首先，為了討論時更直觀，把所有的對應到以I為橫軸，J為縱軸的直角坐標系中的每一個整點上，將橫坐標為i的點稱為第i列的點、縱坐標為j的點稱為第j行的點。(是第i列，第j行的點)若點C是點A與點B的和當C為時，由遞推方程，A、B分別為、。，則連有向邊和(當C為時，由遞推方程，A、B分別為、。IIJA()B()C()123456781230圖A(M=3，N=8)根據遞推關系將所有的邊都連出來，可以得到圖B。IIJD123456781230圖B(M=3，N=8)E觀察要計算的目標，它是與的和，而是與的和；是與的和……可以看出，圖中有很多的點(如圖B中的D，E)的值求出與不求出都不影響最后的答案，所以這些點都沒必要求出，都是冗余的，在圖中也沒必要向這些點連邊。將這些冗余的點和邊刪掉，只留下最后可能影響到目標點的點和邊，圖B變成了圖C的樣子，可以看出，圖C比圖B簡潔多了，要計算的點數(shù)也少多了。IIJ123456781230圖C(M=3，N=8)那么，到底要計算多少個點呢？觀察圖C，發(fā)現(xiàn)當j達到最大，即時第j行只需要計算1個值——；當時第j行要計算2個值——和；當時第J行要計算4個值——、、和……由此可以猜想：①當時第j行要且只要計算個值。②這些要計算的值是這個。這兩個猜想是否正確呢？答案是肯定的，下面用歸納法證明：當時，第j行只要計算，這是顯然的。猜想①、②此時都成立。假設時成立，第j行要計算的為這個數(shù)。

取，當時，由于第j行要計算，由遞推方程，第行要計算，而計算又要用到，計算時要用到……，一直下去，最后所有的都要算出來。

當取遍所有的時，就可以得到第行要計算哪些值，它們是這個數(shù)，這個式子和②的是一樣的。所以此時猜想①、②仍然成立。綜合1°和2°，猜想①、②都是正確的。由①，圖中實際有用的點是個，而開始時計算了個，可見計算過程中的冗余數(shù)目遠遠大于必須計算的數(shù)目。如果去掉這此冗余的計算，算法的時間復雜度可能降到?，F(xiàn)在的問題變?yōu)椋耗男c是要計算的呢？用②找要計算的點固然是一個方法，不過這里有兩個巧妙的結論：③圖中每一列要計算的點必然是最下面的若干個點。因為：如果要計算，從遞推方程看，必定要計算，然后又必定要計算……，直到要計算，最后已知。所以，如果要計算，位于正下方的所有點都要算出來，由此，圖中每一列要計算的點必然是最下面的若干個點。④當i=X時，第i列要計算的點的個數(shù)Ti=X的二進制表示中最末的0的個數(shù)。證明：設i的二進制表示中最末有Ti個0。當j<=Ti時，，即存在整數(shù)，使。因，可得，由②，要計算出來，即第i列至少要計算j個值。特別的，取j=Ti，即可得到第i列至少要計算Ti個值。當j>=Ti+1時，，即不存在整數(shù)，使，由②，不必計算出來。所以第i列只需要計算Ti個值。綜合1°,2°，命題④成立。這樣，時間復雜度降至已不成問題。再看一下空間復雜度。所有不必計算的數(shù)據都可以不分配內存，前面浪費了大量的空間。怎樣才能不浪費呢？假設程序實現(xiàn)時是按照外層循環(huán)從小到大的枚舉i值、內層循環(huán)從小到大枚舉j值的順序，則對于，所用到的值為和，其中是第j-1行的已求出的點中最右邊的點，即當前已求出的(x是非負整數(shù))中x最大的點；是第j行已求出的點中最右邊的點，即當前已知的(x是非負整數(shù))中x最大的點(如圖D)，這是顯然的?？梢韵氲剑瑢τ谀硞€j，只要保存已求出的中x最大的那個元素即可，這樣可以減少浪費，而且能起到類似滾動數(shù)組減少空間的效果?？臻g復雜度可以降到。IIJ123456781230圖D(M=3，N=8)F[i,j]F[i,j-1]F[i-2j,j]已求出的點未求出的點不必求的點2.3.可設，其中，這時，計算的目標是，由，又由于(或者說不存在)，，可將所求的目標改為。仍然將對應到坐標系中，連邊，去除其中的冗余，得到圖E(其中N=5)。添加共r列，令它們的值全為0(圖F)。然后將所有的點向右平移r個單位，得到的就是類似的情況了，但從第0列至第r-1列的值全為0，其他列都滿足的遞推關系(如圖G)。變換之后可順利的求出答案。IIJ01234512圖EF[N,M-1]F[N,M]IIJ-2-1012345123-3圖FIIJ123456781230圖G2.4小結回顧此題，由于開始時做了大量冗余的操作，使得時空復雜度相對于最后的時空復雜度高了很多，當減少冗余后，時空復雜度低了很多。可見，減少冗余是優(yōu)化本題的關鍵。此題還有沒有更好的算法呢？有直接的公式可用嗎？探索中...三最大獎品價值3.1問題描述作為今年年度消費最高獎獲得者，你有機會參加一個促銷性的抽獎游戲。該游戲是這樣的：有N+2級樓梯，從0至N+1標號，從第1級到第N級每級上都放著一個獎品，如果你從第0級走M步(M≤N+1)正好到達第N+1級樓梯，且不走出這N+2級樓梯，你所走過的樓梯上的獎品就是你的了，否則將得不到任何獎品。首先，你給所有的獎品打了一個分值，這些分值都是正整數(shù)。你希望得到的獎品的分值和最大，應該怎么走呢？當然，一步不可能走太多級的樓梯，因為那樣有可能摔著，假設每步最少走0級(即原地不動)，最多走K級(即向樓梯標號增大的方向最多從第i級走到第i+K級，向樓梯標號減小的方向最多從第i級走到第i-K級)。3.2數(shù)學模型原題可如下表示有一個整數(shù)序列，其中，，對于一個和K，從序列中找出一個子序列，使：1)2)；3)最大3.3粗略分析原問題只說了每一步最多走的級數(shù)，沒有規(guī)定是否能往回走。那么往回走有沒有意義呢？假設往回走了，即出現(xiàn)p，使，找出滿足的最小的p，因，所以，若將變?yōu)?，即變換和的位置，仍會滿足要求，且分值的和不變。按照這種方法調整，可以使。因為除外其他的分值大于0，在某級樓梯上停留不如走到一級未走過的樓梯，所以進一步可以使。做了上面的處理后，本題變成了一個最優(yōu)子結構的問題，可以用動態(tài)規(guī)劃解決。用表示所選的第個數(shù)為所能得到子序列的和最大是多少。則。此算法的狀態(tài)數(shù)為，決策數(shù)為K，所以時間復雜度為。這個算法還能優(yōu)化嗎？3.4減少冗余當計算和時，分別要計算和，而可以看出：計算了兩次。如果能減少這種冗余計算，復雜度將能夠降低。如何處理呢？通常，會有三類方法處理：第一類方法：設計算時所得的最大值為，當計算時，將與比較，如果兩個數(shù)不相等，則必有，所以計算時的最大值為，只要即可轉移；但當時，就不得不計算。復雜度為。對于這一類方法，當數(shù)據比較特殊時，如，總時間復雜度是。沒有從根本優(yōu)化。第二類方法：用堆、線段樹之類的數(shù)據結構優(yōu)化。時間復雜度可降到。但編程復雜度將有所提高。第三類方法：首先，分析動態(tài)規(guī)劃的轉移過程，對整個過程進行分析似乎難以下手，因此可以分析一部分，不妨分析從到移的這一步。注意到，若，且，當計算時，因為有在，最大的值不可能取(當是最大值時，可以取而不取)，因此在計算時可不必枚舉——是冗余的狀態(tài)。如果用一個線性表存儲中所有要枚舉的狀態(tài)，且按標號(數(shù)組的第二維下標)從小到大排序，則所有這些狀態(tài)的值將是單調遞減的，這時所求的最大值將是線性表中的第一個元素的值。但怎么實現(xiàn)呢？把線性表改造一下①改造后的線性表在項榮璟的論文中出現(xiàn)過。就可以了：當變大時，線性表中所有的都要刪除(實際上，由于是以1為增量的，最多將線性表的第一個元素刪除)；然后將插入線性表的最后，在插入的過程中，為了保持線性表中的數(shù)單調遞減的特點，若，要將刪除，這些元素都是在線性表的末尾，可以從最后逐一刪除。這個數(shù)據結構中，每個最多進入一次隊列，最多出一次隊列，查找最大元素的復雜度為O(1)。所以總的時間復雜度為。下面是一個轉移的例子：①改造后的線性表在項榮璟的論文中出現(xiàn)過。F[i-1]=(63528)k=3j操作隊列最大值開始[]1插入6，直接插入[6]62插入3，直接插入[6，3]63插入5，5比3大，將3從線性表最后刪除，5插入到最后位置[6，5]64將6從線性表的第一個位置刪除；插入2，直接插入[5，2]55插入8，8比2、5大，將2、5刪除，8插入到最后位置。[8]83.5小結這道題中，冗余并不像整數(shù)拆分那么容易去除，這時，可以考慮利用數(shù)據結構。同時也看到，數(shù)據結構并不時一塵不變的，只要靈活運用，它必能發(fā)揮很大的作用。在減少冗余操作的過程中，往往要利用到數(shù)據結構。四總結從上面的例子可以看到：在算法設計和編程過程中，冗余的出現(xiàn)是難以避免的。冗余是高效率的天敵，減少冗余，必然能使算法和程序效率提高很多(例1時間復雜度由降到、空間復雜度由降到，例2時間復雜