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

Question

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

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

len那么我想知道，考虑to的时间复杂度是否正确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)是一个不同的故事，因为它不会调用 ;__max__上的单个魔术方法obj。相反，它会迭代它，调用__iter__然后调用__next__. 它执行此操作 n 次（并且每次都会进行比较以跟踪迄今为止看到的最大项目），因此它必须始终至少为 O(n)。__next__（如果比较方法很慢，则速度可能会更慢，尽管这是非常不寻常的。）

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