(一) 96 台大電機 Every full binary tree with 50 leves has how many vertices? 這一題 我今天想了一下 full binary tree 定義成 leves皆在同一層高度(k) 而且也必須是complete tree 那我只要算 高度 0~k-1 的所有點 在加上 50的leves 就可以算出所有點 答案是 99 高度必須要是 6 (2^6 = 64 才能滿足所有leves 皆在同一層) 所以答案就是 2^0+2^1+2^2+2^3+2^4+2^5+50 1 + 2 + 4 + 8 + 16+ 32+50=113 和答案不對 不知道我哪裡想法錯了.... (二) 96成大資工 f(n)=4^lgn + n + 3n^1/lgn 我想知道 3n^1/lgn 怎麼算複雜度??? (三) Hn = 1/1 + 1/2 + .... + 1/n is O(lg n) 解答是: 對Hn 做積分 =ln n Hn - 1 < ln n Hn < 1+ ln n Hn =O(lg n) 那 Ω 的寫法可以這樣寫嗎?? 對Hn 做積分 =ln n Hn + 1 > ln n Hn > ln n - 1 Hn =Ω(lg n) 不好意思 我的程度不好 還希望各位大大能夠多多指導 -- 一切.... 似乎都不再那麼重要.... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.230.2.61 ※ 編輯: lovefo 來自: 125.230.2.61 (02/03 12:48)