Fibonacci
Fibonacci本身就是一個recursion，所以學過遞回的人直覺上會寫成和數學式相符合的recursive program:
不過這個事實上重複計算了很多recursions！所以非常慢（正確的running time要用master theorem才能估計出）。
反而沒學過遞迴的人寫出的直覺iterative program可以在linear time (應該是asymptotically n^2 runtime) solve:
這個等於是用了額外的記憶體F array來換取縮短執行時間
最大公因數GCD
最大公因數如果很天真直覺地用for loop來測試1到a+b的話：
雖然是linear time algorithm，但是應該有更好的方法？ （其實上面的for loop應該從a+b開始往下跑比較快）
要改良的方法是發現更多的數學上的關係（euclidean gcd lemma)：
所以我們可以快速縮減每次input到gcd()的a,b值：
根據lemma寫成的program，是一個recursive program，執行時間相當於log(a*b)，非常大的改進：
wow....是不是很有趣啊？！
沒有留言:
張貼留言