「干貨筆記」算法評價與復雜度
在算法競賽中，一道好的算法競賽題目可以通過對一個程序評分，區(qū)分出「好的算法程序」和「不那么好的算法程序」。而評價一個算法，也有著一定的計算模式和標準。利用這個標準，就可以評價一個算法程序是否優(yōu)秀——從而預判這個算法的可靠程度，并作出調整和優(yōu)化。
? 如何去評價一個算法？
算法競賽中，為測試一個選手的程序，一般采用的是「黑箱測試法」：即在進行測試時，將程序看作是一個不能打開的「黑盒子」。只需將輸入數(shù)據(jù)扔進這個黑盒子里，觀察它返回的結果是否正確，至于程序內部如何實現(xiàn)則并不關心。
對于算法競賽的評價機制來說，選手需要在規(guī)定的時間內實現(xiàn)題目所要求的程序，且程序須在限定的時間與內存之內給出測試數(shù)據(jù)所對應的答案。于是，對選手的程序就有了以下要求：
代碼可實現(xiàn)
即能夠將算法通過代碼實現(xiàn)出來。如果能想出一個算法卻無法實現(xiàn)，或者是不能在比賽限定的時間內將其實現(xiàn)，都是不符合要求的。
結果需正確
程序需要能夠正確運行并輸出正確的結果，才能通過題目的測試點。
運行不超時
除了需要結果正確，運行用時應當越短越好。對于數(shù)據(jù)量大的題目，需要盡力去優(yōu)化程序運行用時，否則將難以通過測試點。
資源不超限
一臺計算機的運算資源是有限的，所以資源占用也應當越少越好。
顯而易見，前兩點是作為一個合格程序的前提。對于一個算法，更重要的則是它的時間復雜度。
? 什么是時間復雜度？
在實際測試之前，一個程序是無法準確估計其運行時間的。但是，幾乎所有的算法競賽的題目中都會明確地告知將輸入數(shù)據(jù)的規(guī)模和運行時間的限制。而選手就可以通過分析算法的時間復雜度，從而預計是否能夠在限定的時間內運行完算法程序。下面是一個簡單的例子：
例題?質數(shù)是指除了1和本身之外沒有其他約數(shù)的數(shù)，如7和11都是質數(shù)，而6不是質數(shù)，因為6除了約數(shù)1和6之外還有約數(shù)2和3。給定n個正整數(shù)a，輸出質數(shù)的個數(shù)。對于所有測試數(shù)據(jù)，0<n≤200，0<a≤10?.。
例如，當輸入是
應當輸出 2
子任務1 (10分)：n≤1, 0<a≤10?.
子任務2 (30分)：n≤200, a≤10*
子任務3 (60分)：n≤200, a≤10?
思路1：?最直接的思路就是枚舉所有a可能的因數(shù)，代碼十分的簡單：
那么，這個程序運行需要多久呢？程序的運行時間和輸入的數(shù)據(jù) a 有關，畢竟數(shù)據(jù)越大，計算的時間就越長。不過現(xiàn)在，可以通過分析這一份代碼估計它要運行多少次語句。
在這里，當 a 較大時， if(a%j==0) 這條判斷語句就要運行很多遍。對于某一語句，計算需要運行多少次時，可以在這條語句后加上一個全局計數(shù)器變量，每運行一次就自增1，最后輸出這個計數(shù)器即可得到這條語句的運行次數(shù)。
當然，亦可通過數(shù)學推導的方式得到這個數(shù)據(jù)。十分明顯的，對于單個數(shù) a ，這個算法最多枚舉的次數(shù)應為 a-2 ，我們把算法需要執(zhí)行的運算次數(shù)用函數(shù)表示，即 T(a) =a-2 。此時為了估算算法需要的運行時間和簡化算法分析，我們引入時間復雜度的概念。
定義：存在常數(shù) c 和函數(shù) f(N)，使得當 N >= c 時 T(N) <= f(N)，表示為 T(n) = O(f(n)) 。
當 N >= 2 的時候，f(n) = n^2 總是大于 T(n) = n + 2 的，于是我們說 f(n) 的增長速度是大于或者等于 T(n) 的，也說 f(n) 是 T(n) 的上界，可以表示為 T(n) = O(f(n)) 。
因為 f(n) 的增長速度是大于或者等于 T(n) 的，即T(n) = O(f(n)) ，所以我們可以用 f(n) 的增長速度來度量 T(n) 的增長速度，所以我們說這個算法的時間復雜度是 O(f(n)) 。
算法的時間復雜度，用來度量算法的運行時間，記作: T(n) = O(f(n)) 。它表示隨著輸入大小n 的增大，算法執(zhí)行需要的時間的增長速度可以用 f(n) 來描述。
拿到算法的執(zhí)行次數(shù)函數(shù) T(n) 之后，怎么得到算法的時間復雜度呢？
在執(zhí)行次數(shù)中，常數(shù)項對函數(shù)的增長速度影響并不大，所以當 T(n) = c，c 為一個常數(shù)的時候，這個算法的時間復雜度就為 O(1)；如果 T(n) 不等于一個常數(shù)項時，即直接將常數(shù)項省略。
例如，對于 T(a) =a-2 ，其時間復雜度即為 O(a)。
其次，高次項對于函數(shù)的增長速度的影響是最大的，故而直接忽略低次項。
例如，在 T(n) = n^3 + n^2 + n + 114 中，n^3 的增長速度是遠遠大于?n^2 的，對于?n 同理，時間復雜度就為 O(n^3)。
而且，因為函數(shù)的階數(shù)對函數(shù)的增長速度的影響是最顯著的，所以也直接忽略與最高階相乘的常數(shù)。
例如，當 T(n) = 3n ^ 514時，時間復雜度為 O(n^3)。
總而言之：如果一個算法的執(zhí)行次數(shù)是 T(n)，那么只保留最高次項，同時忽略最高項的系數(shù)和常數(shù)后得到函數(shù) f(n)，此時算法的時間復雜度就是 O(f(n))。
回到?T(a) 上來，這個算法的時間復雜度即為 O(a)。但是，這一段代碼的執(zhí)行次數(shù)也與 n 有關。在 子任務2 的情況下，最多將運算 200*10* = 2x10? 次。在一般的家用計算機，每秒可以進行數(shù)千萬到數(shù)億（10?數(shù)量級）的運算。所以，這個算法的運算次數(shù)是十分危險的，子任務3是的。
思路2： 不如試著去砍掉多余的枚舉次數(shù)？可以先將所有2以外的偶數(shù)砍掉，且可以發(fā)現(xiàn)偶數(shù)以及大于 a/2 的因數(shù)枚舉都是沒有必要的：
可以看到，這份代碼削減了十分多的枚舉次數(shù)，但仍應按最壞的結果計算，可以得到 T(a) = (a/2-1)/2 ，時間復雜度仍為 O(a)? 。計算次數(shù)約為?1x10??，應可通過子任務2，但對于子任務3則遠遠不夠——將運算?1x10??次。
思路3： 還能再快一點嗎？事實上，枚舉到 √a 就足夠了，可以大大地減少枚舉次數(shù)：
此時，T(a) = (√a-1)/2 ，時間復雜度則為 O(√a)。這樣，只需運算 2x10* 次即可，已經(jīng)可以完全勝任這道題目。
當然，還有更快的方式！——
大于3的質數(shù)有一個特點，即總是等于 6x-1 或者 6x+1 （x為正整數(shù)），所以只需以6為步長枚舉因數(shù)就可以減少很多工作量。當然，還有很多更高效的算法，這里就不再贅述。
不難看出，數(shù)據(jù)量越大，用時也就越多。而在不同的算法下，不同的時間復雜度隨數(shù)據(jù)量的增長是不一樣的：有的算法對數(shù)據(jù)量的增長是十分敏感的，例如 O(n3)?或?O(2?) 甚至是 O(n!) ，后兩者即使 n 只有幾十，運算次數(shù)就已經(jīng)達到了天文數(shù)字，這也是很多搜索回溯算法不能處理稍大規(guī)模數(shù)據(jù)的原因；有的算法則對數(shù)據(jù)量增長不敏感，例如 O(n log n) 或是 O(n) ，一些人類高質量算法甚至可以接近于常數(shù)級復雜度。以下則是一些常見的時間復雜度量級，按執(zhí)行效率從高到低排列：
常數(shù)階O(1)
對數(shù)階O(log N)
線性階O(n)
線性對數(shù)階O(n log N)
平方階O(n2)
立方階O(n3)
K次方階O(n^k)
指數(shù)階(2?)
到了這里，其實運行速度還可以再快一點，不過——應當優(yōu)化的在于輸入部分。
使用cin讀入的速度比較慢，而使用scanf讀入可以加快速度（復雜度不變），這在需要輸入大量數(shù)據(jù)時尤為明顯。
兩者區(qū)別在于，使用scanf輸入元素時，作為一種格式化輸入，已經(jīng)提前告知輸入的數(shù)據(jù)類型，而不需要每次輸入時判斷元素類型；而用cin輸入數(shù)據(jù)時須每次判斷數(shù)據(jù)類型，作為一種字符流輸入，需要先存入緩沖區(qū)再輸入，故而速度較慢，但可以保證讀入的安全性。
當然，也可以自己實現(xiàn)一些「快速讀入」的方法，例如用 getchar 等實現(xiàn)數(shù)據(jù)輸入以加快讀入速度。而這些不改變算法復雜度但可以加快程序運行速度的方法被稱為常數(shù)優(yōu)化。（當然，常數(shù)優(yōu)化的方法還有很多，例如內存優(yōu)化等）
實際上，O(n) 算法相對于 O(n log n) 算法的效率并沒有 log?n 倍提升，且在數(shù)據(jù)量越多時優(yōu)勢越小，這是因為 O(n) 算法的執(zhí)行次數(shù) T(n) 還帶有常數(shù) k?（難以用定量來求出，但程序執(zhí)行的語句的越多，k就會越大），從而抵消了和對數(shù)級別算法的優(yōu)勢。對于小規(guī)模數(shù)據(jù)，常數(shù)對于運行時間的影響并不大；而當數(shù)據(jù)規(guī)模規(guī)模較大時，就不能不考慮常數(shù)帶來的影響。
對于一個進階的選手來說，常數(shù)優(yōu)化是一項十分重要的技能。淺舉一例：當 n=1000 時，0.01n<100n log? n?，在數(shù)據(jù)量并不大的時候，努力優(yōu)化并降低一個高復雜度算法的常數(shù)，比一些大常數(shù)的低復雜度算法常常運行得要更快。下面是一個快速讀入整數(shù)函數(shù)的例子：
『還有更多常數(shù)優(yōu)化的方法，這些將在以后講到』
事實上，無論測試數(shù)據(jù)規(guī)模有多小，運行一個程序仍需要數(shù)毫秒的時間。因為在運行程序前，需要一些時間進行初始化工作，例如分配內存資源等，而這些初始化的時間與數(shù)據(jù)規(guī)模無關。如果一種算法的運算次數(shù)與數(shù)據(jù)規(guī)模無關，則它的時間復雜度是常數(shù)級別的，即 O(1) 。一些算法不使用循環(huán)語句，而是使用一些公式計算答案，這些可能就是 O(1) 復雜度的算法。
通過以上的例子，大家應該都明白并了解了什么是時間復雜度以及計算時間復雜度的方式，并且可以使用時間復雜度作為評價算法效率的一項重要參考指標。一些算法或者程序設計競賽的題目會給出測試數(shù)據(jù)規(guī)模不等的子任務，從中我們可以看出題目要求的復雜度，并根據(jù)這些信息以選擇合適的算法，盡可能多地通過各個測試點。不過不幸的是，時間復雜度并不能充當你的應急食品（）。
? 空間復雜度有什么作用？
說到空間復雜度，作為評價一個算法的優(yōu)秀程度的另外一個重要標準，它與算法程序占用內存空間的大小有關。比起時間復雜度，空間復雜度往往并不怎么受到關注。多數(shù)情況下內存的限制一般是幾百兆字節(jié)，還是比較寬松的，而這并非說明內存空間可以隨意敞開了用：只要內存使用超過了上限，即便在規(guī)定的時間里給出了正確的答案，亦是不能得分的。所以，除了注意算法的運算效率，還需要關注程序的內存使用是否超限。
一個程序的空間復雜度是十分容易估計計算的。設立數(shù)組、使用STL容器儲存內容、調用遞歸函數(shù)、創(chuàng)建動態(tài)對象等都會占用內存，其中設立數(shù)組最容易計算內存空間的占用。
例如，一道題目設定的空間上限為 128MB ，一個 int 數(shù)據(jù)使用4個字節(jié)的內存，理論上則可以存下32000000個 int 類型的數(shù)字。顯然，一般讀入并儲存數(shù)據(jù)所占用的空間大小與數(shù)據(jù)的規(guī)模是呈線性關系的，空間復雜度為 o(n) 。而內存占用亦可以進行常數(shù)優(yōu)化，在答案正確的前提下降低內存空間的使用，從而控制程序運行內存不超限。
再例如，輸入數(shù)據(jù)的規(guī)模是n，而需要建立一個 nxn 大小的二維數(shù)組儲存時，空間復雜度就為 O(n2) 。計算一下，可知128MB的內存最多能夠儲存 5600x5600 的 int 二維數(shù)組（實際僅計算常數(shù)訪問次數(shù)，巨大的時間復雜度亦會導致其用時過長），故而應當謹慎創(chuàng)建一個 n [100000][100000] 這樣的二維大數(shù)組，而多維數(shù)組則亦應更為謹慎，我們應提前計算規(guī)劃好需要使用的內存空間，并要防止其超限。
要注意的是，為了增加難度，一些題目也會對內存空間作出嚴格的限制，甚至限制到只有數(shù)兆字節(jié)的內存。這些題目往往數(shù)據(jù)量很大，故而無法設立數(shù)組儲存，只能夠讀入數(shù)據(jù)后當即處理后丟棄，這就對算法和思維的考驗更高了。
關于「非完美算法」的那些事
在大大小小的程序競賽中，每一位選手都希望能夠以自己有限的能力水平?jīng)_刺更多的分數(shù)。一些競賽中，要求選手的程序必須通過所有的測試點才能獲得分數(shù)，例如國際大學生程序設計競賽（ICPC）；而一些競賽中，則將題目分出數(shù)個子任務，按點計分，故而程序僅滿足部分測試數(shù)據(jù)時，也能獲得部分的分數(shù)，例如全國青少年計算機程序設計競賽。我們可以通過選擇一些適當?shù)牟呗?，以獲得高的分數(shù)。
當難以作出題目的正確解法時，我們可以 直接擺爛 就部分子任務寫出一個「非完美算法」，從而取得盡量多的部分分數(shù)。以下是一些方法：
完成小數(shù)據(jù)范圍的高復雜度方法
在一道算法競賽題目中，每個子任務的數(shù)據(jù)范圍是有梯度的。如果找不到能夠符合題意的正解，則可以試著以枚舉、搜索等基本低效率算法完成題意。盡管算法時間復雜度高，亦能通過較小數(shù)據(jù)范圍的子任務以取得一定分數(shù)。
嘗試解決部分的特殊情況
部分的子任務會規(guī)定一些特殊的情況，例如樹狀數(shù)據(jù)結構退化為鏈狀結構、過于復雜的情況不存在等。此時可以通過針對特殊情況專門解決這些子任務，雖然算法并不符合題意，但對于這些特殊情況是正解，從而可以降低對于題目的思維難度。
在一道題目中可能有數(shù)種特殊情況，這時可以針對不同的特殊情況作出對應的算法，而后判斷輸入數(shù)據(jù)符合的情況，并通過適當?shù)乃惴▽ｉT解決這些特殊情況，從而靈活獲得力所能及的分數(shù)。
使用近似算法
近似算法中包括隨機算法、啟發(fā)式搜索等，盡管可能不能夠得到正確的答案，但可以得到比較理想的結果，效率也不低。算法選擇得當?shù)耐瑫r加上一點好的運氣，甚至亦能夠獲得題目分數(shù)。如果前兩種都走不通時，就可以使用近似算法試試（指不定就撞了大運了呢）
在平時練習的時候不一定非要以通過某一道題目為標的，也可以嘗試難度大點的題目，分析觀察每一個子任務，通過一些非完美算法以盡可能多的完成它們，并通過各種方法優(yōu)化算法的復雜度，從而接近甚至完成正解。
到了這里，先?挖個坑?：
關于常數(shù)優(yōu)化的若干方法
各個STL容器的介紹
（暑期更新）
