※ 引述《taitin (小南)》之銘言： : 這是我自己寫的答案，希望跟大家討論一下 : 附上題目 : http://www.lib.ntu.edu.tw/exam/graduate/98/98404.pdf : 1. (1) G G(跟你同) : (2) H F : (3) L D : (4) E E(跟你同) : (5) H 原本想I ，不過我驗算後改H compute(n,1): 第一小題 X為 【5】 Y為 【n/4取下限】 Z為 【n*n^(1/2)】 第一個for x←1～5 要做5次遞迴compute(n/4取下限, x*t) 每個遞迴的下面還要再做5次遞迴... ... .. 至於遞迴的次數有多深 端看 【Y不斷的(n/4取下限)，何時到達<=1】 那就是5^(log n) = n^(log 5) 4 4 第二個for z←1 ~ n*n^(1/2) 每次處理 1單位時間 theta(1) 就是theta(n*n^(1/2)) 答案: theta ( n^(log 5) ) + theta( n*n^(1/2) ) 4 (右邊的成長比較快) => O(n*n^(1/2)) 選G ------------------ 第二小題 X為4 Y為 n/2取下限 Z為 n^2 第一個for x←1～4 4次遞迴... 遞迴的次數深度....取決【Y不斷的(n/2取下限)，何時到達<=1】 => 4^(log n) =>n^(log 4) => n^2 2 2 第二個for z←1 ~ n^2 => theta(n^2) 答案: theta(n^2) + theta(n^2) =>選項中最接近的答案是 O(n^2) 選F --------------- 第三小題 第一個for : theta( n^(log 3) ) 2 第二個for : theta( n*log n ) 2 theta( n^(log 3) ) + theta( n*log n ) 2 2 右邊的成長比較快~ => O(n*log n) 2 選D ---------------(省略部分的字~好懶) 第四小題 第一個for : 2^(n/2) (成長較快) 選O(2^n) E 第二個for : n --------------- 第五小題 n^(1/2) 第一個for : (用剛剛的方法很難算) n^ 後續寫不出來 改成T(n) = n * T( n^(1/2) ) = n * n^(1/2) * T( n^(1/4) ) = n * n^(1/2) * n^(1/4) * T( n^(1/8) ) = n * n^(1/2) * n^(1/4) * n^(1/8) * T( n^(1/16) ) = n * n^(1/2) *....... ( 1+(1/2) +(1/4)+ (1/8) +....+(1/n) ) =n^ 逼近 n^2 => O(n^2) 第二個for : (n^2)* log n 2 所以第二個成長較快 選H ㄧ起來討論看看唄~ -- 學長學長!那邊有飆車族 學長學長!那邊剛好像有女生 學長學長!那邊有人紅燈右轉 砍人 被壓上車 ψQSWEET 鴿 ◥ 鴿 ◥ 鴿 ◥ 鴿 ◥ 鴿 ◥他媽的◤ 鴿 ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 攔下來呀!⊙ ⊙◥ ◥ ◤ ◥ █◤ ◥ ◤ ◥ 3◤╯ξ ◥ ◤沒王法了◥皿 ◤ ◥ ◥◥ (哈欠)◤ ◥◤ ◥ ◥◥ (煙~) ◤ ◥ ◤￣ ◥ ◥◥是不是?!(◥ ◤ ◤) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.227.125.142 ※ 編輯: qazwsxee 來自: 61.227.125.142 (01/23 00:05) ※ 編輯: qazwsxee 來自: 61.227.125.142 (01/23 00:50)