[理工] [algo]-觀念問題

看板Grad-ProbAsk作者 (Ace)時間14年前 (2010/03/04 14:15), 編輯推噓11(11推 0噓 13→)
留言24則, 8人參與, 最新討論串1/1
一、If we have proved that the lower bound of an NP-complete problem is polynomial, then we have proved that NP = P. 二、The worst case time complexity of finding the second minimum key in an n-key heap is？ 三、Radix sort can only be performed on sequential list, not on link list. 四、Searching for a key in a heap takes worst case time O(n). 其中第一、三、四是(True/False)，第二為時間複雜度， 麻煩解答了，感謝。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.57.79.11
推
03/04 14:19, , 1F
1.F 2.logn
03/04 14:19, 1F
推
03/04 14:27, , 2F
第三題我之前寫過 手邊解答是F
03/04 14:27, 2F
推
03/04 14:35, , 3F
1.錯在upper bound
03/04 14:35, 3F
推
03/04 16:05, , 4F
第二題我覺得是O(n)
03/04 16:05, 4F
→
03/04 16:12, , 5F
樓上是覺得skew嗎? 還是..?
03/04 16:12, 5F
→
03/04 16:13, , 6F
第二題我會寫O(1)，因為最多找兩次(root的左右子點)
03/04 16:13, 6F
→
03/04 16:15, , 7F
O(1)應該會錯吧 因為題目沒有指名是哪種heap 而且worst
03/04 16:15, 7F
※ 編輯: assassin88 來自: 61.57.79.11 (03/04 16:17)
推
03/04 16:18, , 8F
通常max heap只提供find max，不然就兩種都寫+說明
03/04 16:18, 8F
推
03/04 17:01, , 9F
第二題是O(logn)，做兩次extract min就好了
03/04 17:01, 9F
推
03/04 17:28, , 10F
沒說這個heap是MAX還是MIN，找最小的是n是
03/04 17:28, 10F
→
03/04 17:28, , 11F
第二小的是n+logn-2次
03/04 17:28, 11F
→
03/04 17:28, , 12F
請看18125篇 次
03/04 17:28, 12F
→
03/04 17:29, , 13F
所以是O(n)
03/04 17:29, 13F
推
03/04 17:46, , 14F
不行吧 應該O(log n) 若說沒有說最大或最小heap
03/04 17:46, 14F
→
03/04 17:46, , 15F
那很多題目若沒有直接說min or max 則 找到
03/04 17:46, 15F
→
03/04 17:46, , 16F
O(n) 的worst 答案
03/04 17:46, 16F
推
03/04 18:00, , 17F
樓上說什麼@@?
03/04 18:00, 17F
推
03/04 18:12, , 18F
抱歉剛剛~學校電腦時間快到了~打太快= =
03/04 18:12, 18F
→
03/04 18:12, , 19F
我不太認同沒有說min 或max便要花O(n)找到最小
03/04 18:12, 19F
→
03/04 18:13, , 20F
heap不管怎麼說都是complete tree調整 search都只花樹高
03/04 18:13, 20F
→
03/04 18:14, , 21F
不可能需要找最小就比較N次 調整樹高也頂多log n
03/04 18:14, 21F
→
03/04 18:31, , 22F
樓上可以試試min-heap找max跟max-heap找min
03/04 18:31, 22F
推
03/04 18:38, , 23F
= =總覺得這題目.....算了 寫答案的時候我都會寫吧
03/04 18:38, 23F
→
03/04 18:39, , 24F
頂多註明清楚就是了 這應該比較保險
03/04 18:39, 24F
‣ 更多 assassin88 的文章
文章代碼(AID): #1BZq__qE (Grad-ProbAsk)