※ 引述《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)