c++ - 简单的单链表复杂度查询

Question

我们知道在单链表上查找是 O(n) 给定一个头指针。假设我始终在链表的一半处维护一个指针。我会改善任何查找时间吗？

Answer 1

是的，只要您有某种方法可以确定是从列表的开头还是中间开始（通常但不一定是要排序的列表），它可以将复杂性降低 2 倍。然而，这是一个恒定因素，因此就大 O 复杂性而言，它是无关紧要的。

要与大 O 复杂性相关，您需要的不仅仅是恒定的因子变化。例如，如果你有一个指针来平分每一半，然后再平分每一半，依此类推，你最终会得到对数复杂度而不是线性 - 你会把你的“链表”转换成一个（已经众所周知的）线程树。

Answer 2

不错的想法，但这仍然不能改善搜索操作。无论您在列表的不同部分有多少指针，您仍然必须分析列表中的每个元素。但是，您 - 可以 - 两个线程搜索列表的每一半，从而使操作在理论上快两倍。

Answer 3

仅当您的链接列表的数据已排序时。否则，正如另一个答复中已经说过的那样。

Answer 4

它会，但渐近地它仍然是一样的。但是，有一种数据结构使用了这种思想，它被称为跳过列表。跳过列表是一个链表，其中一些节点有更多的指针，这些指针在某种意义上指向列表其余部分的中间。这张图片很好地说明了这个想法。这种结构通常具有对数插入查找和删除。