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

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

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

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

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

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