推 bernachom:謝謝您，我來算看看^^ 11/10 09:34
※ 編輯: jameschou 來自: 140.113.139.83 (11/10 10:50)
推 bernachom:好詳細，謝謝幫忙^^ 11/10 11:23
※ 引述《jameschou (DOG)》之銘言：
: ※ 引述《bernachom (Terry)》之銘言：
: : 不好意思，請教一下一些問題..
: : 這題可以用老大定理解嗎?
: : 1.T(n)=2T(n/4)+1
: 應該可以
: 因為a=2 b=4 => log a = 0.5
: b
: 0.5 0.5
: 又 n = 1 * n (也就是ε可取0.5) =>可用
: => T(n) = θ(√n)
: : 然後以下幾題是對數學歸納或代入法感覺比較差的題目...
: : 2.
: : http://ppt.cc/klHE
: : 3.
: : http://ppt.cc/!Yng
: : 4.
: : http://ppt.cc/6,AS
: : 希望各位前輩可以幫個忙，教導一下
: : 謝謝指導了。
: 後面這三題我不太懂你是要做什麼@@..
: 因為題目上都有告訴你希望你用什麼方法解或用什麼方法驗證
: 那不一定是最好的方法
: 有時候只是題目就是要你這麼作而已..
我這三題稍微重點寫一下就好
2.
(這題log的底都當2)
你可以先用master method看一下 發現T(n)=nlogn
然後你再假裝你一眼就看出它是nlogn來作數學歸納法
當n=2時 T(2) =2 =2log2 成立
設n=2^k成立 => T(2^k)=2^k(k)
當n=2^(k+1)時
T(n) = 2*T(2^k)+n=2*2^k(k)+(2^k)*2 = (k+1)*2^(k+1) = nlogn成立
所以成立
3.
也可以先用master method看 然後再去畫遞迴樹確認
這題的樹長的很正常 不是歪的 應該不難畫才對
最後再照他說的用代入法
/***趁現在吃早餐比較有空 補充一下***/
這題中我用到的log一樣都是以二為底
log3 1.585
這題其實用master method很輕鬆就可以看出答案是 n ≒ n
但這題也不需要用master method
這題直接照他的方法畫遞迴樹:
level sum
n ╲ ... n
▕
/ | \ ▕
(n/2) (n/2) (2/n) ▕ ... n(3/2)
/ | \ / | \ / | \ ▕共logn層
(n/4)(n/4)(n/4) ..... ▕ ... n(3/2)^2
. ▕
. ▕ .
. ▕ .
1 1 1 1 ............................ ╱
n[(3/2)^logn - 1 ] n[3^logn/2^logn - 1]
再把每層的和加起來 = -------------------- = ----------------------
(3/2) - 1 (1/2)
又 2^logn = n , 3^logn = n^log3
n^log3 log3
=> 和 = 2*n*(-------- -1) = 2*n^log3 - 2n = θ(n )
n
用代入法驗證:
設T(n/2) = c*(n/2)^log3 , c is a constant
n^log3 log3
=> T(n) = 3*[c*(n/2)^log3]+n = 3c*-------- + n = c*n^log3 + n = θ(n )
2^log3
大致上應該是這樣
你可以把它寫更詳細些
4.
這題是要你寫演算法的pseudocode
而且是用暴力法 (非暴力法的話其實只要O(n)就可以)
暴力法也很容易
先設最大值0
然後用兩層迴圈 把從任一數字開始 任何長度的加總都算出來
沿路作只要比目前最大值大 就將最大值改成該值
如此一來跑完的時候存的最大值就是最大和了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.177.7