[理工] [資結]-96清大-資工所

[yesa315 (XD)]

http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/96/2101.pdf

我想問第二題
                                                     2
說要worst case 所以想法是 T(n) = T(n-1) + n    T(k)=k

我把它想像成輸入是sorted 當剩k個 data 用insert 需k^2 的worst case

不知可不可@@

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.127.208.96
推 Lautreamont:這題我是想說merge sort要分兩邊
→ Lautreamont:所以我列式: T(n) = 2T(n/2) + n , T(k)=k^2
→ Lautreamont:解出來: T(n) = n*k + n*log(n/k)
→ Lautreamont:所以我寫 O(nk)
→ Lautreamont:另外之所以遞迴式會寫成T(n/2)是因為洪兔的課程中
→ Lautreamont:說merge sort的worst case式nlogn 所以我只算
→ Lautreamont:insertion sort的worst case
推 FRAXIS:T(n)解出來 要求k值使得T(n)最小
推 EntHeEnd:請問樓上 使T(n)最小的k值要怎樣求...
→ Lautreamont:想用微分解，但是得到的函式會讓k變負的= =