[C Programming] 快速Fibonacci數算法-延伸(中)

延伸問題：
2. (續上題) 請評估一下上一個習題程式的時間值，
    當k愈來愈大時，計算時間會以什麼方式增加；
    這個方法與上一個問題中習題3的做法相比又如何呢？

答：
我們每次算k階矩陣的相乘時，
每個元素需要用到k個乘法，k-1個加法。
一共有k^2個元素，如果乘法花費m單位時間，加法為p單位時間，
總時間最多則為(2 log n)*(k^2)((m+p)k-p)。 (底數為2)
在k越大的狀況下這個時間會以k^3的樣子增長。
比較起上一個問題的k階算法，
概念是每次往後推一直推到f(n,k)，
每次要算k項的加總為k-1次的加法，
全部要做的次數為k+1~n，為n-k次，
總共為(n-k)(k-1)p次。

結論：
當計算時是n dominates的時候，現在這個快速算法，
會比前面使用加法來得吃香。
但當k dominates的時候，這個算法的時間就會花的比之前的方法兇。