Python 中列表访问的时间复杂度是多少？

Question

我正在尝试尽可能快地创建一个 python 函数。假设我有一个素数列表，并且我正在为同一个 i.

调用 primes[i] n 次

我的直觉是，从 n 的某个值开始，将 primes[i] 的值保存在变量中会变得更容易。

我通过比较以下两个实现进行了一些尝试，但我无法确定哪个是最快的。看起来访问 primes[i] 的时间取决于很多因素。

第一次实施

while n != 1:
            p = primes[i]
            if n % p == 0:
                n = n // p
                factorization.append(p)
            else:
                i += 1

第二次实施

while n != 1:
            if n % primes[i] == 0:
                n = n // primes[i]
                factorization.append(primes[i])
            else:
                i += 1

是否有任何规则可以从多少次调用中得知将列表元素的值保存在变量中变得有趣？

Answer 1

访问 primes[i] 是在恒定时间内完成的，O(1)。这意味着读取 primes[i] 所需的时间不会随着 primes 变大而增加，并且当 i 变大时也不会增加。 通俗地说：这太他妈快了！

再一次，访问局部变量p仍然比访问primes[i]快，因为后者必须查找并调用[=13=的__getitem__实现] 目的。因此，将值缓存在局部变量中而不是查找列表两次要快一些。

另一方面，与降低算法复杂度相比，关注边际速度改进毫无意义。对于寻找素数的问题，您应该专注于寻找智能算法而不是改进内置列表访问时间。

Answer 2

尝试使用基准测试

import time

start = time.time()
while n != 1:
        p = primes[i]
        if n % p == 0:
            n = n // p
            factorization.append(p)
        else:
            i += 1
end = time.time()
print(end - start)

对实施 2 执行相同的操作并进行比较。

此外，请尝试在 google colab 或任何其他外部机器中执行此操作以获得更好的结果。

Python 中列表访问的时间复杂度是多少？

What's the time complexity of list access in Python?

python

list

time-complexity