如何理解链表中Find(x)的时间复杂度是Theta(1)

Question

我在读这本书的时候遇到了这个问题，但是我不明白。我们不是仍然需要通过比较列表来找到一个特定的元素吗?谢谢。

Answer 1

是的。我不确定你书中的链表包括哪些属性，但有可能(使用索引或其他策略)使搜索速度超过O(n)。关于搜索优化的更多信息，请访问http://en.wikipedia.org/wiki/Linked_list#Speeding_up_search。