(一) 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)