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

Question

我正在尝试尽可能快地制作 python 函数。假设我有一个主要列表，并且我为此调用primes[i]了 n 次i。

我的直觉是，从 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

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

标签： pythonlisttime-complexity

Answer 1

访问primes[i]是在恒定时间内完成的，O(1). 这意味着阅读所需的时间primes[i]不会随着primes变大而增加，并且不会随着i变大而增加。 用外行的话来说：这该死的快！

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

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