演算法與資結：Big O學習整理

老實說，對Big O這章節我讀了兩次，兩次之間隔了快3週，跑去算了些數學再回來。為了防止以後每次要重想學了什麼，趁剛讀完做個整理。因是重點整理，細節的「為什麼」就先不寫了，怕模糊焦點。

整理大綱：
point 1. 學術界和業界所說的「O(Big O)、Θ(Big theta)、Ω(Big omega)」定義有何差別？要用哪種去判斷演算法效能？

point 2. O/Θ/Ω 和最佳/最差/預期情況有何關係？

point 3. 計算Big O時需大概考慮哪些面向以求得最後的Big O結果？

point 4. 學習計算Big O時需用到的一些實用數學？

point 5. 一些常見排序演算法的Big O是什麼？

point 6. 給個例子算算看？



以下分點說明：

point 1：
a. Big O：在學術界用來描述時間上限。e.g. 如果今天某演算法的執行時間可說成O(n)。那麼如果說成O(n的平方)或O(2的n次方)都對。但這麼說沒有什麼意義。

b. Big omega：在業界和學術界皆用來描述時間下限。e.g. 如果今天某演算法的執行時間可說成Ω(1)，那我們可確定它已經是最快的執行時間了。

c. Big theta：在學術界中的Θ同時表示O和Ω，也就是說「如當某演算的執行時間是O(n)和Ω(n)，就可當成Θ(n)」。而在業界中會合併O和Θ，也就是說「業界中說的Big O接近學術界中的Θ」，這樣能對演算法的執行時間給個最緊、最接近描述，較有意義。

注意：因而今後提到Big O都是較接近學術界中的Θ。


point 2：
兩者沒特別關係。
a. 最佳/最差/預期情況是指：描述特定輸入/狀況下的Big O。

b. Big O、Big omega、Big theta是指：單純描述某演算法執行時間的上/下限。


point 3：
1. 也需考慮「空間複雜性」：也就是還要看演算法需要的記憶體（或空間量）。e.g. 常常遞迴在未優化下用到的stack較多。

2. 降低常數：e.g. 當我們算出某演算法為O(2n)，可簡化為O(n)。

3. 降低非優勢條件：e.g. 當我們算出某演算法為O(n + log n)，可簡化成O(n)；又或者為O(5*2的n次方 + 1000*n的100次方)，可簡化成O(2的n次方)。


point 4：
1. 基本多項式、因式分解的運算和作圖。

2. 基本指數和對數的運算和作圖。

3. n的n乘冪加總，e.g. 2的0次方 + 2的1次方 + 2的2次方 + ... + 2的n次方 = 2的n+1次方 - 1

4. 整數1~n的加總。


point 5：
如merge sort為O(n log n)，而二元搜尋是O(log n)，因某演算法往往可分為多個部分去計算時間後，再加總成最後的總執行時間，因而這些常見演算法一旦學過其Big O後，就稍記一下，之後便可加快計算整體Big O的結果。


point 6：
這個遞迴題，可討論其「執行時間」和「需要用到的記憶體空間」，其中空間部分，有問過網路上的大大們，得到不錯的解釋。也順便了解了「尾呼叫」和「尾遞迴」是什麼。

e.g.

int f(int n) {
    if (n <= 1) {
        return 1;
    }
    return f(n-1) + f(n-1);
}

解答：
執行時間：O(2的n次方)。因為共有2的n+1次方 - 1個節點被呼叫，得到O(2的n+1次方 - 1)，簡化後：O(2的n次方)。

需要的記憶體空間：O(n)。因任一時間只有出現O(n)個。
=> 其實當初卡關在為何不是O(2的n次方)個，因為「每呼叫一次函式，就會產生一個stack」。後來得到答案：「跟編譯器執行順序有關」。遞迴情況下，可能先執行某一側f(n-1)，和編譯器的巡訪有關。不像人的想法是「一次拆兩邊弄完」。而是先執行一側f(n-1)完成後，先回收記憶體，再繼續執行另一側的f(n-1)。

最後，選了一個簡單易懂的尾呼叫和尾遞迴說明連結：
關於尾呼叫和尾遞迴 --
https://www.itread01.com/content/1545312794.html