※ 引述《lovefo (lovefo)》之銘言： : (一) 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 : 和答案不對 : 不知道我哪裡想法錯了.... 因為最後一層的leaves只有36個 另外14個是上一層的 我的算法是 令X為最後一層的leaf數 N為上一層的leaf數 X + N = 50 X/2 + N = 2^k(k為上一層的level) 兩式相減得 X = 100 - 2^(k+1) 因為X小於50 所以X = 36 剩下就跟你一樣 高度必須為6 1 + 2 + 4 + 8 + 16 + 32 + 36 = 99 : (二) 96成大資工 : f(n)=4^lgn + n + 3n^1/lgn : 我想知道 3n^1/lgn 怎麼算複雜度??? n^1/lgn = (n^lg2)^1/lgn = (2^lgn)^1/lgn = 2 : (三) : 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) : 不好意思 我的程度不好 : 還希望各位大大能夠多多指導 Hn = 1 + 1/2 + 1/3 +...+1/n >= ∫1/x dx = ln n Hn = Ω(ln n) 他本來就比較大了 不用加1 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 124.8.12.227 ※ 編輯: supergud 來自: 124.8.12.227 (02/03 15:09)