作者haniwang (hani)
看板Grad-ProbAsk
標題[理工] 106 清 資演
時間Thu Feb 7 22:17:56 2019
https://i.imgur.com/2MJshSy.jpg
想請問這題如何用big-O notation去表示？
https://i.imgur.com/xdj9ePR.jpg
loading factor是指slot數嗎？
麻煩各位了！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.0.113
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549549078.A.514.html
推 magic83v: n/sb 應該是指佔了多少 02/07 22:46
→ GeniusPuddin: AVL解出一般式後估上界可得 height = O(logn) 02/07 22:49
→ kaidi620: 第一題:AVL最少點數為 兩個子樹高度差1 02/08 13:00
→ kaidi620: 所以，遞迴式為 Nh=Nh-1 + Nh-2 +1 (h,h-1,h-2為index為 02/08 13:01
→ kaidi620: 樹高), +1則是因為最後要加上root點 之後就是解遞迴囉~ 02/08 13:02