[理工] [離散]-一些問題
(一) 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)
推
02/03 13:42, , 1F
02/03 13:42, 1F
→
02/03 13:42, , 2F
02/03 13:42, 2F
推
02/03 17:05, , 3F
02/03 17:05, 3F
推
02/23 23:50, , 4F
02/23 23:50, 4F
討論串 (同標題文章)