python - 理解 python 的 len() 时间复杂度

Question

我有一个问题，关于我是否正确理解了 Python 中 len 函数的时间复杂度。我看过关于此主题的多个帖子 here和 here但我觉得答案没有明确回答我的另一个问题。

据我了解，调用len函数的时间复杂度是O(1)，因为对象(例如数组)的长度存储在场景。但是，调用未存储在幕后的函数(例如 max 或 min)的时间复杂度为 O(n)，因为我们将不得不搜索整个数组。

我想知道，将 len 的时间复杂度也考虑为 O(n) 是否正确(因为它需要 n 当我们从数组中添加或删除值时跟踪数组长度的常量操作数)但仅为 O(1) 因为我们跟踪后面的长度场景？

从技术上讲，我们应该能够在创建数组时存储其他信息，例如 max 和 min 并且访问这些信息也将是 O(1 ) 如果我们明确保存这些值。

Answer 1

len(obj) 简单地调用 obj.__len__():

>>> [1, 2, 3, 4].__len__()
4

因此说 len() 总是 O(1) 是不正确的——在大多数对象上调用len() (例如列表)是 O(1)，但任意对象可能以任意低效的方式实现 __len__。

max(obj) 是另一回事，因为它不会在 obj 上调用单个神奇的 __max__ 方法；它会迭代它，调用 __iter__ 然后调用 __next__。它执行了 n 次(并且每次都进行比较以跟踪到目前为止看到的最大项)，因此它必须始终至少为 O(n)。 (如果 __next__ 或比较方法很慢，它可能会更慢，尽管这很不寻常。)

对于其中任何一个，我们都不将构建集合所花费的时间计算为调用操作本身的成本的一部分——这是因为您可能构建一次列表然后调用 len( ) 很多次，并且知道 len() 本身非常便宜，即使构建列表非常昂贵也是很有用的。