好程式的迷思
一個程式好不好通常看你要解決的問題。
- 時間花得少(運行速度) ex:網頁跑很快、資料載入快
- 空間花得少 ex:硬體不夠充裕，要使用比較少記憶體
- 正確率較高 ex:防毒軟體隊攻擊作防範、更高機率偵測
- 相容性較高 ex:好延伸擴充、裡面程式太複雜造成很難擴充
- 開發成本低 ex:開發軟體時，很快的做法但寫起來很困難，普通速度的作法但寫起來容易。
所以要適當的平衡，並不是哪種一定是好。
相容性、開發成本，通常仰賴當下開發者評估。
正確率則是在實作的細節上、Case量、理論分析上。
複雜度概念
把所有操作都視為一樣的時間，如:加減乘除、位運算、存取記憶體、判斷運算子…等
把所有操作次數計算出來。
看量級大小，來評估執行時間。有些程式容易TLE超時就是因為這問題，比較在意的是量級，而不是精確的值。
舉例:被指派長期作業，有兩種方案可選:
- 每天算10題。
- 第一天算1題，第二天算2題，第三天算3題…。
兩種方案怎麼選?
如果每算一題要5秒
第n天:
- 10 * n * 5 = 50n
- (n+1) * n/2 * 5 = 2.5(n^2+n)
n=5天時，
- 250秒
- 75秒
n=365天時，
- 18250秒
- 333975秒
可以發現操作數的量級(複雜)比較多，所以以長期來看會是方案1比較好。
量級概念
成長的速度不同等級。
如f(n)與g(n)兩個函數，當n趨近無窮大，誰會比較大?
- 3n^2+n+20 vs 100n 如果n = 10000，左邊會變成億；右邊只有百萬，所以左邊量級大
- n^100 vs 2^n
- n^2 vs 10nlogn
- 100^n vs n! 如果n=200，左邊100倍，右邊成長200倍，所以右邊量級大於左邊。
- 30*2^n vs 3^n
- 100n vs 200n 同一量級，因為極限的概念
極限概念
如果f(n)/g(n)，n趨近無限大時趨近0，那麼說f(n)比g(n)小。
如果f(n)/g(n)，n趨近無限大時趨近無限大，那麼說f(n)比g(n)大。
否則稱作兩者一樣量級。
所以，100n/200n = 1/2，所以不管n多大都一樣，稱作一樣量級。
但是，科技進步可以補100n與200n的差異，如平行運算可能可以把100n與200n的作法都視為一樣。但如果不是同一量級，還是會有科技進步彌補不了的，如上面的例子1。
量級的比較
以一台每秒可以進行10億次運算的電腦:
所以好算法、壞算法需要的時間是有很大差距的。
大歐符號 Big-O
記為O(f(n))，f(n)為複雜度量級的”上界”。所以實際結果可能會比他還要小。
常數會省略只寫一個n
- 3n^3+5n^2+10n+3 ∈ O(n^3)
- f(n) ∈ O(n^2)，則f(n) ∈ O(n^3)，因為是上界
- 1000 ∈ O(1)
ps.最緊上界:如果一個算法同時是O(n^2)算法、O(n^3)算法，通常會取比較小的O(n^2)，以避免過度悲觀評估。<<=這句我不太懂
- 3n^2+n+20 vs 100n ；O(n^2) vs O(n)
- n^2 vs 10nlogn；O(n^2) vs O(nlogn)
- 100^n vs n! ；O(100^n) vs O(n!)
- 30*2^n vs 3^n ；O(2^n) vs O(3^n)
- 100n vs 200n ；O(n) vs O(n)
常見的時間複雜度函式:
如果時間不穩定
如一個人姓名存在資料庫，想找到那個人
如果是排第一個情況，O(1)
如果是排最後一個情況，O(n)
多數關注的是最壞的case，如:插入排序，最好是O(n)；最壞是O(n^2)
總結
從參考資料中整理的一些對演算法複雜度的知識。
如果有機會寫到要追求「時間花得少」或「空間花得少」時就能派上用場，但這些通常使用在底層實作上，在應用的層面非常少用到，不過能透過理解複雜度，盡量選擇好的實踐方法。
此外，在應用層面上，相容性較高、開發成本低，我認為比較重要；底層函式庫則是追求時間花得少、空間花得少。所以，看是寫哪個層面的程式，如果兩者反過來會蠻可怕的。
參考資料
https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
https://www.youtube.com/watch?app=desktop&v=_r7cfVrn28c
https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6