※ 引述《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)