[理工] [資結]-複雜度

[luckyburgess (the one)]

有底下三個小問題想問各位大大,希望大家可以幫幫忙解答^^

Q1:radix sort可以用sequential list或是linked list來執行嗎?

Q2:"searching for a key in a heap takes worst-case time O(n)"
   這句敘述對嗎?? why??

Q3:"The time complexity of binary search is the same as searching with
    binary search tree"這句敘述對嗎?? why??

麻煩大家了!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.134.213.201
→ aey:1.可以 2.應該是log n (樹高) 3.都是log n
推 FRAXIS:1.可以 2.沒錯, 因為heap沒有像二元數那種順序性
→ FRAXIS:3. 不對, 要平衡的二元樹才是O(lg n)
推 aey:嗯 樓上才是對的
→ polomoss:2. 1~n由小到大建立BST，搜尋就會花O(n)
→ luckyburgess:恩 那請問第一題是兩個都可以嗎??
→ abien:yes