search - 数据结构搜索复杂度

Question

在链表中搜索的复杂度是 O(n)。

在队列或堆栈中搜索也是 O(n)，对吗？

Answer 1

如果它们是无序的，那么是的，O(n)因为在最坏的情况下，您必须检查每个元素。

Answer 2

不完全是。

这取决于您的实施。例如，如果您在队列/堆栈中有一个哈希表，那么您将获得一个“超级”队列/堆栈，其中包含 O(1) 推送/弹出/搜索。