算法分析與枚舉策略

《算法分析與枚舉策略》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、ACMGroup算法分析與枚舉策略程序設(shè)計實踐算法的分析方法簡單性健壯性效率——時間復(fù)雜度占用空間——空間復(fù)雜度算法的時間復(fù)雜度一個算法對特定輸入的時間復(fù)雜性是該算法對該輸入產(chǎn)生結(jié)果需要的基本操作或“步”數(shù)。假設(shè)我們求出算法過程中執(zhí)行基本操作的次數(shù)，為c(n)次。我們進一步規(guī)定在特定計算機上算法的基本操作的執(zhí)行時間為t，則可以估計出整個算法的運行時間T≈t·c(n)。時間復(fù)雜度只能衡量c(n)相對于n的增長速度情況，和t沒有直接關(guān)系。但考慮整個算法的運行時間時千萬不要忽略了基本操作的執(zhí)行時間t。時間復(fù)雜度的規(guī)定設(shè)f(n)是關(guān)于n的函數(shù)，我們用關(guān)于f(n

2、)的一個函數(shù)來表示算法的漸進時間復(fù)雜度。嚴格的定義是這樣的：若存在兩個正常數(shù)c和m，對于任意n>m都有

3、T(n)

4、≤c·

5、f(n)

6、，（這可以看作是極限的思想：n->∞時，f(n)是T(n)的同階或高階無窮大）則稱T(n)在集合O(f(n))中，用O(f(n))表示算法的時間復(fù)雜度。通?？梢哉J為，算法過程中執(zhí)行基本操作的次數(shù)為k時，g是對于某數(shù)的增長情況的函數(shù)，有g(shù)(k)≈g(f(n))，則該算法的時間復(fù)雜度為O(f(n))。O(f(n))中的f(n)的計算c1·

7、f(n)

8、≤

9、T(n)

10、≤c2·

11、f(n)

12、一般來說取滿足上式的f(n)來表示時間復(fù)雜度

13、較為精確。但是滿足條件的f(n)還是很多，為了方便準確的表示時間復(fù)雜度，f(n)應(yīng)用下面的方法求得：令f(n)=T(n),然后忽略常數(shù)和低次項（增長次數(shù)的排序見下張幻燈片）求得f(n)。例如3n^4+8n^2+n+2=O(n^4)，其中f(n)=n^4。關(guān)于時間復(fù)雜度的兩個表AcceptedorTLE一般來說評測機每秒處理基本操作10^8次左右，所以將題目最大數(shù)據(jù)帶入O(f(n))就基本可以估計出是否會超時。試分析三個算法的時間復(fù)雜度1.f[0]=f[1]=1,f[2]=2;for(i=3;i<=n;i++)f[i]=f[i-1]+f[i-3];2.f

14、or(i=1;i<=n;i++)for(j=1;j<=i;j++)if(j==1

15、

16、j==i)f[i][j]=1;elsef[i][j]=f[i-1][j]+f[i-1][j-1];3.for(i=1;i<=n;i++)for(j=1;j<=i*i;j++)f[j]++;試分析三個算法的時間復(fù)雜度算法一的基本操作數(shù)為n-2，時間復(fù)雜度為O(n)。算法二的基本操作數(shù)為（1+2+3+…+n）=n·（n+1）·1/2=1/2·n2+1/2·n，時間復(fù)雜度為O(n2)。算法三的基本操作數(shù)為12+22+32+…+n2=1/6·n·(n+1)·(2n+1)，時間復(fù)

17、雜度為O(n3)。試分析遞歸算法的時間復(fù)雜度intf?(intx){if(x==2)return2;if(x<2)return1;returnf(x-1)+f(x–3);}輸入n計算f(n)試分析遞歸算法的時間復(fù)雜度設(shè)計算f(n)的基本操作數(shù)為g(n)則有g(shù)(n)=g(n-1)+g(n-3)g(0)=g(1)=g(2)=1可知g(n)=C0P0n+C1P1n+C2P2n可知f(n)的時間復(fù)雜度為O(an)空間復(fù)雜度ACM題目對空間方面一般不會有太嚴格的要求，只要保證程序申請的內(nèi)存空間小于題目要求就行了。不過這個不能隨便估計要精確計算。再普及一下應(yīng)該都知

18、道的知識：char=1Bshort=2Bint=4Bdouble=8Blonglong=8B1MB=1024KB=1024*1024B時空權(quán)衡一般來說可以通過花費更多的空間換取更少的時間，或者花費更多的時間換取更少的空間。我們要根據(jù)要求來時空權(quán)衡設(shè)計算法。這一點大家會在今后學(xué)習(xí)更多的算法后得到體會，這里就不深入講解了。枚舉所謂枚舉法，指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗條件判定哪些是無用的，哪些是有用的。能使命題成立，即為其解。枚舉是一種確定范圍后的搜索。枚舉的幾個主要步驟如下：對命題建立正確的數(shù)學(xué)模型；根據(jù)命題確定的數(shù)學(xué)模型中各變量

19、的變化范圍；利用循環(huán)語句、條件判斷語句逐步求解或證明。枚舉的優(yōu)點是簡單、直觀、便于理解和證明。主要缺點就是計算規(guī)模大，效率低下。但枚舉類的題目不一定簡單，在有多種枚舉策略的時候，要分析每種策略的優(yōu)劣，選取最好的策略來滿足題目的要求。簡單的例題HOJ1128HOJ1459例1統(tǒng)計問題x+2y+3z=200，求正整數(shù)解的個數(shù)。三種枚舉方法：可以比較一下優(yōu)劣枚舉x，枚舉y，枚舉z，驗證。枚舉x，枚舉y，驗證200-x-2y整除3。枚舉y，枚舉z，統(tǒng)計即可。例題2時鐘考慮將如此安排在一個3×3行列中的九個時鐘。目標要找一個最小的移動順序次將所有的指針指向12點

20、。下面圖中列出了9種不同的旋轉(zhuǎn)指針的方法，每一種方法都叫一次移動。選擇1到9號移動方法，將會使