为什么在Python中访问列表是O(1)的时间复杂度？

Question

为什么在Python中访问列表是O(1)的时间复杂度？

pythonlistdictionarydata-structurestime-complexity

26

我知道列表和数组是不同的。但是，还是O(1)吗？这意味着在列表中访问一个元素与在字典中访问一个元素一样快，我们都知道这不是真的。

我的问题基于这个文档：

list

----------------------------
| Operation | Average Case |
|-----------|--------------|
|    ...    |     ...      |
|-----------|--------------|
|  Get Item |     O(1)     |
----------------------------
以及这个答案：

在列表中进行查找是O(n)的，在字典中进行查找是摊销后的O(1)，与数据结构中的项目数有关。

如果第一个文档是正确的，那么为什么访问字典比访问列表更快，即使它们具有相同的复杂度？

请问有人能够清晰地解释一下这个问题吗？我会说它始终取决于列表/字典的大小，但我需要更多的见解。

- Diego Mora Cespedes

1

我们都知道这不是真的，难道不是吗？“列表”和“数组”是不同的，真的吗？（你混淆了查找和通过索引访问任意项，这就是“获取项”的含义） - njzk2

4

在列表中访问特定索引处的元素复杂度为*O(1)，但在列表中搜索元素的复杂度为O(N)*。 - Vedang Mehta

1

我认为第一个文档讲的是通过索引访问列表元素，第二个文档讲的是测试成员资格（在列表或哈希支持的集合中）。这些是不同的事情。 - pvg

2

Python的列表在C术语中是数组。它更像是C++中的数组或向量，而不是（链接）列表。 - robyschek

4个回答

28

访问索引为n的列表l的元素l[n]的时间复杂度为O(1)，因为它不是实现为传统的链表，需要在指针(值，下一个-->)之间跳跃n次才能到达索引为n的单元格。

如果内存是连续的，并且条目大小是固定的，那么访问特定的条目将是简单的，因为我们知道要跳过n次条目大小(就像C语言中的经典数组)。

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

更多信息请参见：常见问题解答（FAQ）}，{{link2:可变长度数组（VLA）和动态数组。

- Hanan Shteingart

10

这是因为Python将列表中每个节点的地址存储在一个单独的数组中。当我们想要访问第n个节点时，我们只需要查找地址数组的第n个元素，这将给出列表中第n个节点的地址，通过该地址我们可以在O（1）的复杂度下获取该节点的值。

Python使用一些巧妙的技巧使这些数组能够随着列表的增长而扩展。因此，我们获得了列表的灵活性和数组的速度。这里的权衡是当列表增长到一定程度时，编译器必须重新分配地址数组的内存。 Amit 在他回答这个问题时解释了为什么字典的查找比列表快。

- Faihan

-2

从严格的计算机科学角度来看，我能看到的最小可能是O(log n)

- Dave Crooke

好的，这个问题特别涉及到Python。 - vaultah

这是错误的，哈希表的平均时间复杂度特别是Python的字典是O(1)。如果您对哈希表和平均情况分析不熟悉，我建议阅读一些相关资料，如哈希表和平均情况分析。 - amit

我拥有计算机科学博士学位。你犯了与那些声称基数排序是O(1)的人一样的错误。这是现实...为了使键唯一，最小长度为O(log n)，因此匹配一个键需要O(log n)的时间。如果它们不是唯一的，则哈希桶包含多个项。正如我所说，你在开发者层面思考，大O()是计算机科学，而拥有O(1)数据结构在数学上是不可能的。 - Dave Crooke

我拥有计算机科学博士学位。你犯了与那些声称基数排序是O(1)的人一样的错误，就像我曾经犯过的一样。现实情况是......为了使键值唯一，最小长度为O(log n)，因此匹配一个键需要O(log n)的时间。如果它们不是唯一的，则哈希桶包含多个项。正如我所说，你在开发者层面思考，而大O()是计算机科学，任何类型的数据结构都不可能是O(1)。那些拥有计算机科学本科学位的人可能还记得证明排序唯一键是Omega(n log n)的方法。 - Dave Crooke

2

我同意从理论角度来看，这是严格正确的。但复杂性计算的实际重要性在于其对现实世界性能的影响。在现实世界中，数据结构具有有限的可行大小，并且适当长度的固定大小键就足够了（例如64位键适用于超过10 ** 19个元素），主要关注的是计算时间如何扩展到这些固定大小的键足够的示例。在硬件层面上，可能存在64位并行性，这消除了使用较小键的速度优势。[续...] - Elroch

2

如果64位不够用，128位应该足以应对全球所有计算机数据相当长一段时间，对于所有可行的例子，不超过2倍的因素可以被描述为对于所有实际目的来说都是O(1)。 - Elroch

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

获取项目指获取特定索引上的项目，而查找则意味着搜索列表中是否存在某个元素。要做到这一点，除非列表已排序，否则您将需要迭代所有元素，并具有 O(n) 的“获取项”操作，这导致了 O(n) 的查找。

字典在底层维护一个智能数据结构（哈希表），因此您不需要查询 O(n) 次以查找元素是否存在，而是需要一个恒定数量的查询（平均情况），从而导致 O(1) 的查找。