在链表中查找元素的成本是多少？我知道在平衡二叉搜索树中找到一个元素的成本是 O(log n)，但是链表呢？
问问题
2218 次
1 回答
2
如果您对链表中的元素一无所知并且没有指向链表的指针，则在链表中搜索元素的成本在最好的情况下是 O(1)，在最坏的情况下是 O(n)。在最好的情况下，您会在最前面找到元素，而在最坏的情况下，您必须先查看所有元素，然后才能确定您要搜索的元素不存在。
在最坏的情况下，这比平衡二叉搜索树要慢得多，因此链表上有一些变体旨在加快访问速度。例如，skip list使用多个并行链表来“跳过”列表中的元素。这要求元素按排序顺序存储，但它确实将查找时间减少到预期的 O(log n)。
希望这可以帮助！
于 2013-01-20T20:56:05.403 回答