【正文】 歸程序可以有像O(b N)， O(N!)， 甚至O(N N)的階。 經(jīng)驗(yàn)法則 在分析一個(gè)算法以計(jì)算出對于一個(gè)給定的數(shù)據(jù)集它可能要運(yùn)行多長時(shí)間的時(shí)候，第一條經(jīng)驗(yàn)法則是：現(xiàn)代（1999）計(jì)算機(jī)每秒可以進(jìn)行10M次操作。對于一個(gè)有五秒鐘時(shí)間限制的程序，大約可以處理50M次操作。真正優(yōu)化的好的程序或許可以處理2倍甚至4倍于這個(gè)數(shù)目的操作。復(fù)雜的算法或許只能處理這個(gè)數(shù)目的一半。 640K確實(shí)是苛刻的內(nèi)存限制。幸運(yùn)的是，19992000賽季將是這個(gè)限制的最后一次起作用。 210 約等于10 3 如果有k重嵌套的循環(huán)，每重大約循環(huán)N次，該程序的復(fù)雜度為O(N k)。 如果你的程序有l(wèi)層遞歸，每層遞歸有b個(gè)遞歸調(diào)用，該程序復(fù)雜度為O(b l)。 當(dāng)你在處理有關(guān)排列組合之類的算法時(shí)，記住N個(gè)元素的排列有N!個(gè)，N個(gè)元素的組合或N個(gè)元素組成的集合的冪集的有2 n個(gè)。 對N個(gè)元素排序的最少時(shí)間是O(NlogN)。 進(jìn)行數(shù)學(xué)計(jì)算！將所有的數(shù)據(jù)加起來。（？？原文是Plug in the numbers.） 例子： 一個(gè)簡單的重復(fù)N次的循環(huán)復(fù)雜度為O(N)： 1 sum=0 2 fori=1ton 3 sum=sum+i 一個(gè)雙重嵌套循環(huán)的復(fù)雜度通常為O(N 2)： fill array a with N elements 1 fori=1ton1 2 forj=i+1ton 3 if(a[i]a[j]) swap(a[i],a[j]) 注意，雖然這個(gè)循環(huán)執(zhí)行了N(N+1)/2 次if語句，但他的復(fù)雜度仍然是O(N 2)，因?yàn)镹加倍后執(zhí)行時(shí)間增加了四倍。 解決方案的范例 產(chǎn)生器 vs. 過濾器 產(chǎn)生大量可能的答案然后選擇其中正確的（比如8皇后問題的解答），這樣的程序叫做過濾器。那些只產(chǎn)生正確答案而不產(chǎn)生任何錯(cuò)誤節(jié)點(diǎn)的叫做產(chǎn)生器。一般來說，過濾器較容易（較快）編程實(shí)現(xiàn)但是運(yùn)行較慢。通過數(shù)學(xué)計(jì)算來判斷一個(gè)過濾器是否足夠好或者是否你需要嘗試制作一個(gè)產(chǎn)生器。 預(yù)先計(jì)算 有時(shí)生成表格或其他數(shù)據(jù)結(jié)構(gòu)以便快速查找結(jié)果是很有用的。這種方法叫做預(yù)先計(jì)算（在這里用空間換取時(shí)間）。你可以將需要預(yù)先計(jì)算的數(shù)據(jù)和程序一起編譯，在程序開始時(shí)計(jì)算；也可以干脆記住預(yù)先計(jì)算出的結(jié)果。比如說，一個(gè)程序需要將大寫字母轉(zhuǎn)化為小寫字母，可以不需任何條件地利用一個(gè)表格進(jìn)行快速查找來實(shí)現(xiàn)。競賽題經(jīng)常要用到素?cái)?shù)——生成一長串素?cái)?shù)在程序中某處使用通常是很實(shí)用的。 分解（編程競賽中最困難的事） 雖然在競賽中經(jīng)常使用的基本算法不超過20種，但是某些需要將兩種算法結(jié)合才能解決的組合型問題卻是很復(fù)雜的。盡量將問題不同部分的線索分離開來以便你可以將一個(gè)算法和一個(gè)循環(huán)或其他算法結(jié)合起來以獨(dú)立地解決問題的不同部分。注意，有時(shí)你可以對你的數(shù)據(jù)的不同（獨(dú)立）部分重復(fù)使用相同的算法以有效地改進(jìn)程序的運(yùn)行時(shí)間。 對稱 許多問題中存在著對稱（例如，無論你按哪一個(gè)方向，一對點(diǎn)之間的距離通常是相同的）。對稱可以是2路的（？？原文是2way），4路的，8路的或是更多的。盡量利用對稱以減少運(yùn)行時(shí)間。 例如，對于4路對稱，你只需解決問題的四分之一，就可以寫下4個(gè)結(jié)果，這四個(gè)結(jié)果和你所解決的一個(gè)結(jié)果是對稱的（注意自對稱的解答，他當(dāng)然只應(yīng)該被輸出一次或兩次）。 正向 vs. 逆向 令人驚訝地，許多競賽題用逆向法解決比正面突破要好得多。以逆序處理數(shù)據(jù)或構(gòu)造一種基于某種非明顯的方式或順序檢索數(shù)據(jù)的突破策略時(shí)，要特別小心。 簡化 某些問題可以被改述為一個(gè)有點(diǎn)不同的其他問題，這樣你解決了新問題，就已經(jīng)有了原始問題的答案或者容易找出原始問題的答案；當(dāng)然，你只需解決兩者之中較容易的那個(gè)。另外，像歸納法一樣，你可以對一個(gè)較小的問題的解答作一些小小的改變以得到原問題的完整答案。 Receipted from Translated by Starfish 原文： Crafting Winning Solutions A good way to get a petitive edge is to write down a game plan for what you39。re going to do in a contest round. This will help you script out your actions, in terms of what to do both when things go right and when things go wrong. This way you can spend your thinking time in the round figuring out programming problems and not trying to figure out what the heck you should do next... it39。s sort of like preputing your reactions to most situations. Mental preparation is also important. Game Plan For A Contest Round Read through ALL the problems FIRST。 sketch notes with algorithm, plexity, the numbers, data structs, tricky details, ... Brainstorm many possible algorithms then pick the stupidest that works! DO THE MATH! (space amp。 time plexity, and plug in actual expected and worst case numbers) Try to break the algorithm use special (degenerate?) test cases Order the problems: shortest job first, in terms of your effort (shortest to longest: done it before, easy, unfamiliar, hard) Coding a problem For each, one at a time: Finalize algori