演算法效率與Big oh

要討論一個演算法的效率，可以從空間複雜度和時間複雜度兩方面來分析。

關於空間複雜度，指的是演算法所占用的儲存空間，可以考慮為固定空間與變動空間的總和。固定空間指的是程式用來儲存指令、變數、常數及結構等等所耗費的空間。而可變空間則涉及了程式的輸入大小，或者遞歸呼叫等等所要占用的空間，需要視解決的問題而更動。一般而言，程式所需的全部空間S(P) ＝Sp(I) + c，前者為變動空間，後者c為一常數，屬於固定空間。


關於時間複雜度，考慮的是演算法執行完成要花費多少時間，包括了編譯和執行時間，不過一個程式編譯後能執行多次而不需重新編譯，因此，我們真正關心的是程式的執行時間。至於如何得知執行時間？基本上有兩個方法，一是利用計時程式來幫助我們，例如引入<time.h>，不過這會因硬體設備產生偏差，二是土法煉鋼，計算出程式需要多少個步驟完成，但這又讓我們面臨一個新問題，如何定義一個步驟？
我們先暫且假設一個步驟等同於一個指令，意思是t++這種簡單的指令與t=t+3*a+4*b+5*c這種複雜的計算都為一個步驟，現在。我們已經能藉由一個變數來對一個程式記數，例如：


step告訴我們這個程式共花了103個步驟，如果將50改為一個自由輸入的變數n，那麼步驟總數即為2n＋3次。

題外話，你可能會很好奇為何int i沒有被列入step，因為從系統的角度來看，宣告一個變數只是在編譯時建立一個空間，並不會產生什麼對應的程式碼，除非在宣告時有分配一個值給變數。

不過還記得嗎？先前我們對步驟的定義一點也不精確，即便一行一行的慢慢數，也未必有助於估計效率。換句話說，既然從一開始就是估計，結果也是夠用就好，那麼夠用又是指什麼程度呢？如果從極限的角度出發，在n極大時，2n+3的3影響微乎其微，一兆與一兆零三元相差無幾，進一步而言，an^2+b與cn+d，我們不必精確知道常數a、b、c、d，代表什麼，因為函數的成長趨勢告訴我們，在n突破某個值後，前者所耗費的時間必定會超越後者。當然，不排除在n不夠大時考量效率會做出錯誤判斷，但通常我們在意的往往是相當大的輸入，而不是拘泥幾微秒的差距。

---

Big O notation


談時間複雜度，總是不能忘記他的老跟班Big-Oh，它是一個漸進符號，至於為什麼用Ｏ，有人說是代表Order，有人說是形容你看到它的表情。總之，Ｏ能夠描述函數漸進的趨勢，他的快樂夥伴還有Ω (omega)跟Θ(theta)，不過目前先介紹他們的老大。

1.Big-Oh定義：

f(n) = O(g(n))：存在常數Ｃ、Ｍ，對於所有大於Ｍ的輸入Ｎ，使得f(n)不大於Ｃ*g(n)

簡單來說，f(n)的成長速度不會超過g(n)，頂多跟他一樣快而已。
以上文舉例：f(n) = 2n+3，g(n)=n，則當N大於3時，f(n)不大於3*g(n)，我們便可以說f(n) = Ｏ(n)
再舉一個比較常見的例子：當N>5時，10n²+10 < 11n²，因此10n² +10 = O(n²)

「看，很簡單吧」。「我們在這裡沒有什麼錯誤，只有快樂的意外。」

g(n)怎麼來的？怎麼突然蹦出一個3？4不行嗎？4也是符合答案啊，教科書就這麼討厭4嗎？如果要亂入的話，我也能讓g(n)=99n，這樣我Ｎ＝1的時候也對呀，而且我答案還是f(n) = O(99n)耶。更傷心的是，它還舉了滿滿一頁的例子來嘲諷我，不禁令我回想起童年中那顆超級爆炸頭。

首先，範例就真的只是個範例，他沒有要你求任何東西。先回顧一下定義，f(n)的成長速度不會超過g(n)，換句話說，當n非常非常大的時候，f(n)一定會比g(n)矮，那如果我們把g(n)整形成g'(n)：

g'(n) = g(n)+1，f(n)會不會比g'(n)矮？會

g'(n) = g(n)+2，f(n)會不會比g'(n)矮？當然會

g'(n) = g(n)+2，f(n)會不會比g'(n)矮？肯定會

我們能一直＋＋＋＋＋出各式各樣的g'(n)，當然，g'(n)=2g(n)也是個可行的辦法，定義告訴我們：只要g(n)在座標軸的右端比f(n)高就成了，別去在乎他高了多少。照這樣看來，g(n)會有很多種可能囉？就定義上來看，沒錯，如果符合定義，我們就能舉出各式各樣的答案。

但是，這樣會導致一個問題，答案多樣性，它是生物多樣性的好朋友，常見於作業、考卷讓學生被當掉。
比方說 f(n)=123n+456，那我能說g(n)=n，g(n)＝n²，或者像g(n)=e^n2+5n+8這種奇葩函數，只要能找到適合Ｃ和Ｍ，都算是個解。為了解決這個問題，我們希望g(n)越小越好，如此它才最接近，也最能夠描述逼近的趨勢，所以當f(n)=123n+456n時，我們預期g(n)＝n，而不是n²，儘管這個答案是正確的。

說了這麼多，那要怎麼去預期？

最直觀地去想，找影響趨勢最大的就對啦，我們考慮的是極限，所以攻略目標是一個函式裡，極限值最大的那個，從成長趨勢的大原則說起，

多重指數函數 >  階乘 > 指數函數 > 多項式函數 > 對數函數 > 常函數