dhb*_*lah 2 sorting algorithm data-structures
我想知道,那些性能之间有什么区别,前提是二进制搜索用于排序链表插入,搜索.并且在哪些情况下它们的表现不同或者可能出于某种目的,例如,列表将无法使用,反之亦然.
您不能仅仅因为没有遍历一半(从一端)到达列表中间而无法在链表(单个或双重)上进行二进制搜索.
毫无疑问,这种形式的多级跳过列表可以做到这一点,但在我看来,它只是模拟具有更复杂结构的二叉树.
排序的链表往往是O(n)用于搜索,插入和删除(实际的插入/删除本身是O(1),但您仍然必须首先找到插入或删除点).
或者,二叉树(平衡的树)是用于搜索,插入和删除的O(log n)(所有这些操作都与树的高度成比例).
| 归档时间： |
|
| 查看次数： |
2386 次 |
| 最近记录： |