new*_*int 4 binary-tree
准备考试.这不是功课问题.
我认为最坏的情况是O(N ^ 2)来构建BST.(每次插入req N-1比较,你总和所有的比较0 + 1 + ... + N-1~N ^ 2).这是倾斜的BST的情况.
(平衡)BST的插入是O(log N),那么为什么最好的情况是O(N logN)来构造树？
我猜最好的猜测 - 因为单个插入是log N,而不是总结所有插入以某种方式给我们N log.
谢谢 !
Jan*_*yka 9
正如你所写的:)单个插入是O(log N).因为N元素的加权树高是log N,你需要记录N个比较来插入单个元素.您需要进行N次插入.所以N*logN.
归档时间：
15 年 前
查看次数：
6556 次
最近记录：