Python中创建嵌套列表的时间复杂度

Question

我在使用Python 2.6.6创建嵌套列表时遇到了一些奇怪的事情。

看看下面这两个函数：

def lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = []
    print time.time() - start_time

def simple_lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = False
    print time.time() - start_time

这两个函数都分配了一个大小为n*n的数组。一个把所有值都设为“False”，另一个把所有值都设为空列表。从我能看到的情况来看，它们的运行时间应该都是O(n^2)。但是，似乎并不是这样……看看下面的测试结果：

>>> for i in [4000, 8000, 16000]: simple_lists(i)
2.11170578003
8.67467808723
34.0958559513
>>> for i in [1000, 2000, 4000]: lists(i)
1.13742399216
7.39806008339
78.0808939934

如你所见，simple_lists()的增长大约是O(n^2)，而lists()的增长却超过了O(n^3)！

这是怎么回事呢？这个问题完全打乱了我代码的复杂度，我也无法解释为什么会这样。有没有人能给我一些建议？

补充：列表推导式似乎也会导致同样的复杂度问题。

如果像这样重新定义lists()：

def lists(n):
    start_time = time.time()
    lists = [[[] for y in xrange(n)] for x in xrange(n)]
    print time.time() - start_time

会得到以下结果：

>>> for i in [1000, 2000, 4000]: lists(i)
0.388785839081
4.45830011368
65.6449248791

……这仍然明显增长得比O(n^2)快（甚至比O(n^3)还快，真是让人惊讶）。

补充2：经过进一步调查后，似乎是垃圾回收器导致了这个问题。在运行gc.disable()后，使用原始的lists()定义得到的结果是：

>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266

这明显是O(n^2)的增长。

这个故事的教训是：不要相信垃圾回收器！

Answer 1

先生成第一个列表，这样可以在O(n)的时间内完成。

def simple_list(n):
    import time
    start_time = time.process_time()
    k=[[] for y in range(n)]
    lists = [k for x in range(n)]
    end_time=time.process_time()
    print (end_time - start_time)

Answer 2

在我的电脑上

for i in [1000, 2000, 4000]: lists(i)

得到的结果是

0.994000196457
4.31200003624
17.9900000095

这个结果的复杂度是O(n^2)，也就是说它的运行速度随着数据量的增加会变得比较慢。最后一个操作占用了1GB的内存，而当我尝试处理8000个列表时，硬盘就会忙得不可开交，导致我的电脑出现问题。delnan可能说得对，我建议你检查一下你电脑的可用内存和在运行这个操作时Python的内存使用情况。

Answer 3

原来这个奇怪的表现是因为垃圾回收器在作怪。把它关掉，使用 gc.disable() 后，结果如下：

>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266

这个结果完全符合 O(n^2) 的情况。