[理工] 106 清資演 haniwang PTT批踢踢實業坊

作者: haniwang (hani) 2019-02-07 22:17:56

https://i.imgur.com/2MJshSy.jpg
想請問這題如何用big-O notation去表示？
https://i.imgur.com/xdj9ePR.jpg
loading factor是指slot數嗎？
麻煩各位了！

作者: magic83v (R7) 2019-02-07 22:46:00

n/sb 應該是指佔了多少

作者: GeniusPuddin (GeniusPudding) 2019-02-07 22:49:00

AVL解出一般式後估上界可得 height = O(logn)

作者: kaidi620 (萬能屎哥) 2019-02-08 13:00:00

第一題:AVL最少點數為兩個子樹高度差1所以，遞迴式為 Nh=Nh-1 + Nh-2 +1 (h,h-1,h-2為index為樹高), +1則是因為最後要加上root點之後就是解遞迴囉~

繼續閱讀