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

Question

我知道列表与数组不同.但是,O(1)？这意味着访问列表中的元素与访问dict中的元素一样快,我们都知道这不是真的.我的问题是基于这份文件:

list

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

而这个答案:

列表中的查找是O(n),字典中的查找是分摊的O(1),关于数据结构中的项目数.

如果第一个文档是真的,那么为什么访问一个dict比访问列表更快,如果它们具有相同的复杂性？

有人可以对此作出明确的解释吗？我会说它总是取决于列表/字典的大小,但我需要更多的洞察力.

Answer 1

访问l索引n l[n]处的列表是 O(1)，因为它不是作为普通链表实现的，其中需要在指针 (value, next-->) 之间跳转 n 次才能到达单元格索引 n。

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

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

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

Answer 2

这是因为 Python 将列表中每个节点的地址存储到一个单独的数组中。当我们想要第 n 个节点处的元素时，我们所要做的就是查找地址数组的第 n 个元素，它给出了列表中第 n 个节点的地址，通过它我们可以得到该节点的复杂度值O(1)。

Python 使用了一些巧妙的技巧来使这些数组可以随着列表的增长而扩展。因此，我们获得了列表的灵活性和数组的速度。这里的权衡是，每当列表增长到一定程度时，编译器就必须为地址数组重新分配内存。

阿米特在回答这个问题时解释了为什么字典中的查找比列表中的查找更快。

Answer 3

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

字典是在底层维护一个智能数据结构(哈希表),因此您不需要查询O(n)时间来查找元素是否存在,而是需要固定次数(平均大小写),从而导致O(1)查找.