[理工] 98 清大資應

[SiriusCloud (古月小楓)]

http://tinyurl.com/78elztn


我想請問一下

1.(b)小題 題意是甚麼?

要如何解呢? 看不太懂題目 也不知道從何下手




還有第三題的(b)(c)小題

b小題的題意

答案是 2^n 次方 = 16 -> n = 4嗎?

c小題

我查了wiki 可以在O(1) create heap

那代表答案是 Can 嗎? 還是要再解釋? 如何解釋呢?


------------------------------------------

感覺寫分計概 根本就在考演算法= = ''

麻煩大家幫忙解了 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.46.159.65
推 ahousi:我剛好也想問耶
推 simonjoker:請問你是在wiki的哪裡查到的呢?
→ simonjoker:create heap 就算是best case也是O(n)吧?
推 pikachu123:bottom up建heap是O(n)就linear time不是?
→ SiriusCloud:http://en.wikipedia.org/wiki/Heap_(data_structure)
→ SiriusCloud:所以那題只要回答 yes 就可以了嗎?
→ pikachu123:他那個thata(1) 是建空heap
→ pikachu123:Wiki他那個是Corman書上的
推 simonjoker:阿...我昏頭了 O(n) 是線性沒錯
→ simonjoker:可是題目又說worst case algo?
→ simonjoker:這樣不是O(nlogn)嗎?
推 pikachu123:就Bottom up那個阿 最差O(n) 可以把證明寫上去
→ pikachu123:Top down才是 nlogn
推 simonjoker:喔喔!! 我記錯了!!!!!!!!!!!!!!!
→ simonjoker:Top down是O(nlogn)   Bottom up是O(logn)
推 shenevol:看ptt長知識~
→ SiriusCloud:感謝 我在研究~
→ sneak: 感謝 我在研究~ https://daxiv.com