为什么在 Python 中列表访问 O(1)？

Question

我知道列表不同于数组。但是，O(1)？这意味着访问列表中的元素与访问字典中的元素一样快，我们都知道这是不正确的。我的问题是基于 这个文件：

 list

----------------------------
| Operation | Average Case |
|-----------|--------------|
|    ...    |     ...      |
|-----------|--------------|
|  Get Item |     O(1)     |
----------------------------

这个答案：

列表中的查找是 O(n)，字典中的查找是分期 O(1)，关于数据结构中的项目数。

如果第一个文档为真，那么为什么在具有相同复杂性的情况下访问字典比访问列表更快？

有人可以对此给出明确的解释吗？我会说它总是取决于列表/字典的大小，但我需要对此有更多的了解。

原文由 Diego Mora Cespedes 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

Get item 是获取特定索引中的项目，而 lookup 是搜索列表中是否存在某个元素。为此，除非列表已排序，否则您将需要迭代所有元素，并进行 O(n) Get Item 操作，这导致 O(n) 查找。

字典在底层维护着一个智能数据结构（哈希表），所以你不需要查询 O(n) 次来查找元素是否存在，而是恒定的次数（平均情况），领先到 O(1) 查找。

原文由 amit 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

访问列表 l 在索引 n l[n] 是 O(1)，因为它不是作为跳转指针之间的值实现的, next–>) n次到达单元格索引n。

如果内存是连续的并且条目大小是固定的，那么到达特定条目将是微不足道的，因为我们知道要跳转条目大小的 n 倍（就像 C 中的经典数组）。

但是，由于列表的条目大小是可变的，因此 python 实现仅针对指向值的指针使用连续的内存列表。这使得索引列表 (l[n]) 成为一项操作，其成本与列表的大小或索引的值无关。

有关详细信息，请参阅 http://effbot.org/pyfaq/how-are-lists-implemented.htm

原文由 Hanan Shteingart 发布，翻译遵循 CC BY-SA 4.0 许可协议