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

Understanding python's len() time complexity

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

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

我想知道,将 len 的时间复杂度也认为是 O(n) 是否正确(因为它需要 n 次常量操作来保持当我们从数组中添加或删除值时跟踪数组的长度)但只是 O(1) 因为我们在幕后跟踪长度?

从技术上讲,我们应该能够在创建数组时存储其他信息,例如 maxmin,如果我们显式保存这些信息,访问这些信息也将是 O(1)值。

我们不计算所有递增和递减数组长度字段的操作的复杂性,因为它们不依赖于数组的当前长度。

例如,如果您通过追加和弹出来构建数组,在调用 len().

之前,您可能已经完成了远远超过 n 次迭代

此外,如果您正在计算整个算法的复杂性,您应该已经考虑了创建数组的复杂性。你不想在计算处理数组的复杂度的时候再算一遍。

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() 本身非常便宜,即使构建列表非常昂贵也是很有用的。

让我们检查一下:

import time
from matplotlib import pyplot as plt
import numpy as np


def main():
    a = []
    data = []
    for i in range(10_000):
        a.append(i)
        ts_len = time.time()
        _ = len(a)
        te_len = time.time()

        ts_max = time.time()
        _ = max(a)
        te_max = time.time()

        ts_min = time.time()
        _ = min(a)
        te_min = time.time()

        data.append([i, te_len - ts_len, te_max - ts_max, te_min - ts_min])

    data = np.array(data)
    plt.plot(data[:, 0], data[:, 1], "-r", label="len")
    plt.plot(data[:, 0], data[:, 2], "--g", label="max")
    plt.plot(data[:, 0], data[:, 2], ".b", label="min")
    plt.title("Len/max/min")
    plt.xlabel("Size of the list")
    plt.ylabel("Time elapsed (s)")
    plt.legend()
    plt.show()


if __name__ == '__main__':
    main()