資源描述:
《論文國家隊(duì)胡偉棟》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、減少冗余與算法優(yōu)化長沙市長郡中學(xué)胡偉棟1摘要】在信息學(xué)競賽中,我們經(jīng)常會(huì)遇到冗余,而冗余會(huì)造成算法、程序的效率不同程度的降低:有的是微不足道的,而有的會(huì)導(dǎo)致算法復(fù)雜度大大提高。本文針對(duì)后者,舉例說明冗余對(duì)算法效率的影響和如何減少冗余?!娟P(guān)鍵字】冗余、算法優(yōu)化1正文】引言信息學(xué)競賽屮,我們所追求的口標(biāo)之一,是使程序用最少的時(shí)間解決問題,也就是達(dá)到最高的效率。實(shí)際生活中也同樣需要這樣,高效率者往往會(huì)在競爭中収得優(yōu)勢。冗余,是指多余的或重復(fù)的操作。在搜索、遞推、動(dòng)態(tài)規(guī)劃等諸多的算法中,都會(huì)出現(xiàn)兀余。曲冗余的定義,要使算法達(dá)到最高的效率,必須去除算法中的冗余處理。
2、但完全去除兀余是難以實(shí)現(xiàn)的,使程序用絕對(duì)最少的時(shí)間解決問題也是很難的,通由兀余的定義,常需要退一步,將忖標(biāo)改為:使程序用盡量少的時(shí)間解決問題??梢缘玫剑阂岣咚惴ǖ男?,必須減少算法中的冗余處理。要減少兀余,需要在大量的做題過程屮,不斷探索,不斷積累經(jīng)驗(yàn)。下面就讓我們通過兩個(gè)具體的例子來研究冗余是如何彫響算法效率的以及如何減少兀余。二整數(shù)拆分2.1問題描述①將正整數(shù)N拆分成若干個(gè)整數(shù)的和,使拆分成的數(shù)是2的非負(fù)整數(shù)幕的形式。問有多少種拆分方案。如果兩個(gè)方案僅有數(shù)的順序不同,它們算作同一種方案。如:當(dāng)N=5時(shí),可以拆分成下面的形式:5=14-1+1+1+15
3、=1+14-1+25=1+2+25=1+4①題目來源:金愷原創(chuàng)第1頁共10頁所以,5有4種拆分方案。2.2粗略分析此題可用遞推解決(為什么?請(qǐng)讀者自己思考5用F[iJ]表示i拆分成若干個(gè)數(shù),其中最大的數(shù)不超過2,的拆分總數(shù)。則:1°F[OJ]=12°FfZ,01=1,即I拆分成若干個(gè)數(shù),其屮最大的數(shù)不超過2o=l的拆分方案只有一種:把i拆分成i個(gè)1o3°當(dāng)z>0j>0時(shí),F(xiàn)[i,j]由兩類組成:第一類:拆分成的最大數(shù)止好是2),其總數(shù)為F[i2第二類:拆分成的最人數(shù)小于2j,其總數(shù)為F[iJ1]。所以F[i9j]=F[i2)J]+F[jJl]o最后要計(jì)算的
4、
5、=[標(biāo)是F[N,M]o因?yàn)閕2/必須wO,所以Ilog2/
6、J,又有18/5/Vo不難得出:總的時(shí)間復(fù)雜度是0(N阻2N)①,空間復(fù)雜度也是O(NgN)o看上去,這個(gè)復(fù)雜度已經(jīng)很低了。但是,復(fù)雜度能不能再低一點(diǎn)兒呢?2.3減少冗余為了便于研究,可以首先處理W是2的整數(shù)幕這種特殊情況,然后把N不是2的整數(shù)幕的情況化為N是2的整數(shù)幕的情況處理。2?3?1當(dāng)N是2的整數(shù)次幕時(shí)把所有的F[iJ]對(duì)應(yīng)將橫坐標(biāo)為z的點(diǎn)稱設(shè)N=2m(M為非負(fù)整數(shù))。首先,為了討論時(shí)更直觀,到以I為橫軸,丿為縱軸的直角坐標(biāo)系中的每一個(gè)整點(diǎn)上,為第i列的點(diǎn)、縱坐標(biāo)為j的點(diǎn)稱為第/行的點(diǎn)
7、。是第i列,第丿?行的點(diǎn))若點(diǎn)C是點(diǎn)A與點(diǎn)B的和②,則連有向邊AC和BC(如圖A所示)。①此處所講的時(shí)空復(fù)雜度都忽略了高粹度的因索。因?yàn)楫?dāng)N達(dá)到10000000時(shí)答案也只有60位,這個(gè)數(shù)字是比較小的。?當(dāng)C為F[iJ]時(shí),由遞推方程,A、B分別為F[i2丿J]、F[iJ1]。第2頁共10頁J32C(F[iJ])11])0123456圖A(M=3,N=078I根據(jù)遞推關(guān)系將所有的邊都連出來,可以得到圖BoJD321E0123456圖B(M=3,/V=8)78I觀察耍計(jì)算的冃標(biāo)F[N,M],它是F[N2.w,M]=F[0,M]與F[N,M1]的和,而F[N1]
8、是2mi,M1]與F[N,M2]的和;F[N,M2]是F[N2a/2,M2]與F[N3]的和……可以看出,圖中有很多的點(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ù)也少多了。3210123456781圖C(M=3,N=8)那么,到底要計(jì)算多少個(gè)點(diǎn)呢?觀察圖C,發(fā)現(xiàn)當(dāng)j達(dá)到最大,即j=M時(shí)第丿?行只需要計(jì)算1個(gè)值F[N,M];當(dāng)j=M1時(shí)第j行要計(jì)算2個(gè)值——F
9、N,M1]和F[1]j=M2時(shí)第J行要計(jì)算4個(gè)值——F[-,M2]、F[-2]、F[-,M2]Ii4和F[N9M2J……由此可以猜想:①當(dāng)j=M氐時(shí)第丿行要且只要計(jì)算2,個(gè)值。k這兩個(gè)猜想是否正確呢?答案是肯定的,下面用歸納法證明:1°當(dāng)j=M時(shí),第丿行只要計(jì)算F[N,M],這是顯然的。猜想①、②此時(shí)都成立。k1個(gè)數(shù)。取j'=j=Mk,當(dāng)/=/o時(shí),由于第J行耍計(jì)算F[/o2./,j],由遞推方程,第廣行要計(jì)算F仏2八廣]=F[2*/°2八廣],而計(jì)算川2*厶2?,廣]乂要用到F[(2/o1)*2廠,廣],計(jì)算F[(2/o1)*2?廠,廣]時(shí)要用至IJ
10、F[(2/o2)*2;,/]……,-直下去,最后所有的F[x*2>