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

看板Grad-ProbAsk作者 (XD)時間16年前 (2010/03/09 21:08), 編輯推噓3(3推 0噓 7→)
留言10則, 3人參與, 最新討論串1/2 (看更多)
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
推
03/09 23:00, , 1F
這題我是想說merge sort要分兩邊
03/09 23:00, 1F
→
03/09 23:00, , 2F
所以我列式: T(n) = 2T(n/2) + n , T(k)=k^2
03/09 23:00, 2F
→
03/09 23:01, , 3F
解出來: T(n) = n*k + n*log(n/k)
03/09 23:01, 3F
→
03/09 23:01, , 4F
所以我寫 O(nk)
03/09 23:01, 4F
→
03/09 23:02, , 5F
另外之所以遞迴式會寫成T(n/2)是因為洪兔的課程中
03/09 23:02, 5F
→
03/09 23:03, , 6F
說merge sort的worst case式nlogn 所以我只算
03/09 23:03, 6F
→
03/09 23:03, , 7F
insertion sort的worst case
03/09 23:03, 7F
推
03/09 23:12, , 8F
T(n)解出來 要求k值使得T(n)最小
03/09 23:12, 8F
推
03/09 23:15, , 9F
請問樓上 使T(n)最小的k值要怎樣求...
03/09 23:15, 9F
→
03/09 23:43, , 10F
想用微分解，但是得到的函式會讓k變負的= =
03/09 23:43, 10F
‣ 更多 yesa315 的文章
文章代碼(AID): #1BbaXQxd (Grad-ProbAsk)
‣ 更多 yesa315 的文章
文章代碼(AID): #1BbaXQxd (Grad-ProbAsk)