为什么在Python中使用列表访问O（1）？ [英] Why is a list access O(1) in Python?

问题描述

我知道列表与数组不同。但是还是O（1）吗？这意味着访问列表中的元素将与访问字典中的元素一样快，我们都知道这是不正确的。
我的问题基于此文档：

I understand that a list is different from an array. But still, O(1)? That would mean accessing an element in a list would be as fast as accessing an element in a dict, which we all know is not true. My question is based on this document:

list

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

和这个答案：

列表中的查找为O（n），字典中的查找为摊销O（1 ），
关于数据结构中的项目数。

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure.

如果第一个文档为真，那么为什么

If the first document is true, then why is accessing a dict faster than accessing a list if they have the same complexity?

如果有相同的复杂性，访问字典比访问列表更快吗？请问有人对此有明确的解释吗？我会说这始终取决于列表/字典的大小，但是我需要对此有更多了解。

Can anybody give a clear explanation on this please? I would say it always depends on the size of the list/dict, but I need more insight on this.

推荐答案

获取项目正在获取特定索引中的项目，而查找意味着搜索列表中是否存在某些元素。为此，除非列表已排序，否则您将需要迭代所有元素，并具有 O（n） Get Item操作，从而导致O（n）查找。

Get item is getting an item in a specific index, while lookup means searching if some element exists in the list. To do so, unless the list is sorted, you will need to iterate all elements, and have O(n) Get Item operations, which leads to O(n) lookup.

字典在后台维护着智能数据结构（哈希表），因此您无需查询 O（n）次查找元素是否存在，但次数固定（平均情况），导致 O（1）查找。

A dictionary is maintaining a smart data structure (hash table) under the hood, so you will not need to query O(n) times to find if the element exists, but a constant number of times (average case), leading to O(1) lookup.

这篇关于为什么在Python中使用列表访问O（1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！