演算法第一次小考範圍 遞迴關係式

有鑑於小考將近。。。。所以筆記的補完先暫停一下

以下是我們第一次小考範圍

--------------------------------------------------------------------
其實看完題目也不用想太多

很明顯的可以代上面的公式得到bigO的結果
不過這樣真的是很靠背(其實是老師拿來對答案)，所以還有別的選擇~

可以先觀察這兩題的式子
不難發現他們就是離散數學中的遞迴關係式，那就值覺得多展開幾次來解看看吧！
====================================================================
1.T(n) when n = 3^k ,T(n) = 2T(n/3)+4 T(1)=1

要解這個bigO 就是要先找規律，那就展開試試看吧

2(2T(n/3^2)+4)+4 <-- 第一次展開
2(2(2T(n/3^3)+4)+4)+4 <-- 第二次展開
......
2^k T(n/3^k)+4 * ∑(i from 0 to k){2^i} <-- 第k次展開

這時候將 n = 3^k 帶入

就會得到這樣的結果 2^k　＋　4*(1-2^(k+1) )/(1-2)

很好 這樣就陷入個不知道怎解的狀態了。。。。

於是 試試看把k帶回來變 log(底3) n 

帶進去吧！！
得到
9*2^log(底3) n - 4


根據

替換公式

所以得到 big-O( n^(log(底3) 2) )  ......5倍<---因為取上限所以忽略了

再代上面的公式驗算一下。。。答案正確！
====================================================================

緊接著第二題
2.T(n) when n = 2^k ,T(n) = 8T(n/2)+n^2  T(1)=1
有了上面的經驗我就不贅述了

式子展開後會變成這樣
k^8 T(n/2^k)+4/3+1/(3*4^k-1)

代入 n = 2^k

的到 8^k取bigO後面可忽略

反推 k = log(底2) n

替換 8 log(底2) n

最後會的到big-O(n^3)
與公式結果相同～
結束

====================================================================
後記：
最近太忙錄了筆記補的速度都快趕不上了OrzOrzOrzOrz