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

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

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

第二類：拆分成的最大數(shù)小于，其總數(shù)為。所以。最后要計(jì)算的目標(biāo)是F[N,M]。因?yàn)楸仨?，所以，又有。不難得出：總的時(shí)間復(fù)雜度是此處所講的時(shí)空復(fù)雜度都忽略了高精度的因素。因?yàn)楫?dāng)N達(dá)到10000000時(shí)答案也只有60位，這個(gè)數(shù)字是比較小的。，空間復(fù)雜度也是?？瓷先ィ@個(gè)復(fù)雜度已經(jīng)很低了。但是，復(fù)雜度能不能再低一點(diǎn)兒呢？此處所講的時(shí)空復(fù)雜度都忽略了高精度的因素。因?yàn)楫?dāng)N達(dá)到10000000時(shí)答案也只有60位，這個(gè)數(shù)字是比較小的。2.3減少冗余為了便于研究，可以首先處理N是2的整數(shù)冪這種特殊情況，然后把N不是2的整數(shù)冪的情況化為N是2的整數(shù)冪的情況處理。2.3.1當(dāng)N是2的整數(shù)次設(shè)(M為非負(fù)整數(shù))。首先，為了討論時(shí)更直觀，把所有的對應(yīng)到以I為橫軸，J為縱軸的直角坐標(biāo)系中的每一個(gè)整點(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為時(shí)，由遞推方程，A、B分別為、。，則連有向邊和(當(dāng)C為時(shí)，由遞推方程，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ì)算多少個(gè)點(diǎn)呢？觀察圖C，發(fā)現(xiàn)當(dāng)j達(dá)到最大，即時(shí)第j行只需要計(jì)算1個(gè)值——；當(dāng)時(shí)第j行要計(jì)算2個(gè)值——和；當(dāng)時(shí)第J行要計(jì)算4個(gè)值——、、和……由此可以猜想：①當(dāng)時(shí)第j行要且只要計(jì)算個(gè)值。②這些要計(jì)算的值是這個(gè)。這兩個(gè)猜想是否正確呢？答案是肯定的，下面用歸納法證明：當(dāng)時(shí)，第j行只要計(jì)算，這是顯然的。猜想①、②此時(shí)都成立。假設(shè)時(shí)成立，第j行要計(jì)算的為這個(gè)數(shù)。

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

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