python - 时间复杂度 - Codility - 阶梯 - Python

Question

问题可用here .我的 Python 代码是

def solution(A, B):
    if len(A) == 1:
        return [1]

    ways = [0] * (len(A) + 1)

    ways[1], ways[2] = 1, 2
    for i in xrange(3, len(ways)):
        ways[i] = ways[i-1] + ways[i-2]

    result = [1] * len(A)
    for i in xrange(len(A)):
        result[i] = ways[A[i]] & ((1<<B[i]) - 1)

    return result

系统检测到的时间复杂度是O(L^2)，我不明白为什么。提前谢谢你。

Answer 1

首先，让我们证明运行时间确实是 O(L^2)。我复制了一段你的代码，并以递增的 L 值运行它:

import time
import matplotlib.pyplot as plt

def solution(L):
    if L == 0:
        return
    ways = [0] * (L+5)
    ways[1], ways[2] = 1, 2
    for i in xrange(3, len(ways)):
        ways[i] = ways[i-1] + ways[i-2]

points = []
for L in xrange(0, 100001, 10000):
    start = time.time()
    solution(L)
    points.append(time.time() - start)

plt.plot(points)
plt.show()

结果图是这样的:

要理解为什么这个 O(L^2) 当明显的“时间复杂度”计算表明 O(L) 时，请注意“时间复杂度”本身并不是一个定义明确的概念，因为它取决于哪些基本操作你在数通常基本操作是理所当然的，但在某些情况下您需要更加小心。这里，如果把加法算作一个基本操作，那么代码就是O(N)。但是，如果计算位(或字节)操作，则代码为 O(N^2)。原因如下:

您正在构建前 L 个斐波那契数列。第 i 个斐波那契数的长度(以数字表示)是 Theta(i)。所以 ways[i] = ways[i-1] + ways[i-2] 将两个数字相加大约 i 位，这需要 O(i) 时间，如果你计算位或字节操作。

此观察为您提供了此循环的 O(L^2) 位操作计数:

for i in xrange(3, len(ways)):
    ways[i] = ways[i-1] + ways[i-2]

在这个程序的例子中，对位操作进行计数是非常合理的:随着 L 的增加，你的数字无限大，而且大数字的加法在时钟时间上是线性的，而不是 O(1)。

您可以通过计算斐波那契数 mod 2^32 来修复代码的复杂性——因为 2^32 是 2^B[i] 的倍数。这将对您正在处理的数字保持有限的界限:

for i in xrange(3, len(ways)):
    ways[i] = (ways[i-1] + ways[i-2]) & ((1<<32) - 1)

代码还有一些其他问题，但这会解决速度慢的问题。