[理工] 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点之后就是解递回囉~

继续阅读