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

[assassin88 (Ace)]

一、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
推 lightergogo:1.F  2.logn
推 Lautreamont:第三題我之前寫過 手邊解答是F
推 stevenwin:1.錯在upper bound
推 crazyjoe:第二題我覺得是O(n)
→ assassin88:樓上是覺得skew嗎? 還是..?
→ strangehead:第二題我會寫O(1)，因為最多找兩次(root的左右子點)
→ assassin88:O(1)應該會錯吧 因為題目沒有指名是哪種heap 而且worst
※ 編輯: assassin88      來自: 61.57.79.11          (03/04 16:17)
推 strangehead:通常max heap只提供find max，不然就兩種都寫+說明
推 stevenwin:第二題是O(logn)，做兩次extract min就好了
推 crazyjoe:沒說這個heap是MAX還是MIN，找最小的是n是
→ crazyjoe:第二小的是n+logn-2次
→ crazyjoe:請看18125篇                          次
→ crazyjoe:所以是O(n)
推 abc73021:不行吧  應該O(log n) 若說沒有說最大或最小heap
→ abc73021:那很多題目若沒有直接說min or max 則 找到
→ abc73021:O(n) 的worst 答案
推 crazyjoe:樓上說什麼@@?
推 abc73021:抱歉剛剛~學校電腦時間快到了~打太快= =
→ abc73021:我不太認同沒有說min 或max便要花O(n)找到最小
→ abc73021:heap不管怎麼說都是complete tree調整 search都只花樹高
→ abc73021:不可能需要找最小就比較N次  調整樹高也頂多log n
→ zkdzvy22:樓上可以試試min-heap找max跟max-heap找min
推 abc73021:= =總覺得這題目.....算了  寫答案的時候我都會寫吧
→ abc73021:頂多註明清楚就是了  這應該比較保險