Algorithms筆記 3 - Big-O

Actual Runtime

我們無法預測一個program的實際執行時間，因為那牽涉到了執行程式的軟體環境和硬體架構等的所有細節條件，所以我們想要知道的是，我們的program是不是scalable? 想知道當input size變大的時候，我們的執行時間會怎麼變化？

不過可以確定，通常不同電腦執行程式的速度差異只會是一個常數級的差別，（不過有時候常數很大...例如一般PC 和超級電腦的差別）。

Asymptotic Runtime

一個program的asymptotic runime在n非常大的時候，會有天差地遠的差別（遠超過常數級別的差異）：

Asymptotic runtime就是在看一個演算法的runtime成長趨勢如何。

Big-O Notation

f is Big-O of g的意思是f這個runtime 函數被g bound在下，所以g至少是c*f。正確定義如下：

如果f <= c * g，而h和g有相同最高次項，我們通常會把O(g)簡化成O(h)，因為h和g有相同的asymptotic runtime（只有常數倍數的差異）。

注意事項！

Big-O只有在比較演算法的asymptotic runtime時有效，但是如果實際input n size並不大，那不見得要選asymptotic runtime小的演算法，因為可能過了某個input size k之後才有runtime優勢，而常用的input size可能遠小於k。

另一個要注意的是，兩個演算法即便都是同樣的O(g)，可是常數倍數差異可能很大（即便只差兩倍也是很大），這時後當然要選常數項越小者，因為實際跑起來就是有倍數的差距。

Fibonacci asymptotic analysis

(1)

這是O(n)，因為每個memory cell可能要被初始化成0，而每個初始化的動作應該是個固定常數runtime，所以是O(1)，做了n次，就是O(n)


(2)

簡單的assignment動作一定都是constant runtime，所以是O(1)


(3)

loop部分牽涉到每個iteration要做i <= n以及 i++的operation，所以是n*O(1) = O(n)。
loop body乍看應該要是O(1)，但是這邊分析成O(n)是因為F[i]的數其實是跟著n長大的，fibonacci number有可能會大到一個machine word不能表達，所以addition operation所花的時間會隨著n增加，所以分析成O(n)，這是比較特別的地方


(4)

這沒有疑問是O(1)

所以這個Euclidean Fibonnaci asymptotical runtime =

我之前以為loop body是O(1)，所以以為整體應該是O(n)，看來錯了，所以naive recursion版本的fibonacci會比O(n^2)更慢!