Re: [理工] [離散]-一些問題
※ 引述《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)
討論串 (同標題文章)