[理工] 98 清大資應

看板Grad-ProbAsk作者 (古月小楓)時間14年前 (2012/01/04 22:17), 編輯推噓7(7011)
留言18則, 6人參與, 最新討論串1/1
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

01/04 22:24, , 1F
我剛好也想問耶
01/04 22:24, 1F

01/04 22:57, , 2F
請問你是在wiki的哪裡查到的呢?
01/04 22:57, 2F

01/04 22:59, , 3F
create heap 就算是best case也是O(n)吧?
01/04 22:59, 3F

01/04 23:32, , 4F
bottom up建heap是O(n)就linear time不是?
01/04 23:32, 4F

01/04 23:34, , 6F
所以那題只要回答 yes 就可以了嗎?
01/04 23:34, 6F

01/04 23:35, , 7F
他那個thata(1) 是建空heap
01/04 23:35, 7F

01/04 23:35, , 8F
Wiki他那個是Corman書上的
01/04 23:35, 8F

01/04 23:52, , 9F
阿...我昏頭了 O(n) 是線性沒錯
01/04 23:52, 9F

01/04 23:53, , 10F
可是題目又說worst case algo?
01/04 23:53, 10F

01/04 23:53, , 11F
這樣不是O(nlogn)嗎?
01/04 23:53, 11F

01/04 23:54, , 12F
就Bottom up那個阿 最差O(n) 可以把證明寫上去
01/04 23:54, 12F

01/04 23:54, , 13F
Top down才是 nlogn
01/04 23:54, 13F

01/05 00:59, , 14F
喔喔!! 我記錯了!!!!!!!!!!!!!!!
01/05 00:59, 14F

01/05 01:00, , 15F
Top down是O(nlogn) Bottom up是O(logn)
01/05 01:00, 15F

01/05 18:01, , 16F
看ptt長知識~
01/05 18:01, 16F

01/06 02:16, , 17F
感謝 我在研究~
01/06 02:16, 17F

09/11 14:43, , 18F
感謝 我在研究~ https://daxiv.com
09/11 14:43, 18F
文章代碼(AID): #1F15-9vt (Grad-ProbAsk)