在python中使用concat运算符创建列表的复杂性

Question

我开始学习数据结构+算法,我遇到了一个问题.这是我正在测试的功能:

def create_list_with_concat(n):
    l = []
    for i in range(n):
        l = l + [i]

这是我的思维过程:我知道毗连运算符是O(k)其中k被添加到原来的名单列表的大小.由于我们一次只添加一个字符列表,因此大小k总是1在这种情况下,所以concat操作需要1一步.由于循环迭代n次数,算法将执行n步骤 - 1每次迭代执行步骤.因此,算法的时间复杂度将是O(n).该算法的实际执行时间会看起来像T(n) = dn这里d是需要进行级联的时间.对于这样的函数,我希望以下是真的:当你将输入大小增加10倍时,输出(执行时间)将增加10倍,因为:

(x, dx) --> (10x, 10dx) --> 10dx/dx = 10

但是,当我实际测试实际值的算法并计算执行时间时,这似乎并没有发生.相反,当我将输入大小增加10倍时,输出(执行时间)增加100倍,而当我将输入大小增加100倍时,输出增加10000倍.这些输出表明二次时间函数和O(n squared).

这是我的完整代码:

import timeit
def create_list_with_concat(n):
    l = []
    for i in range(n):
        l = l + [i]

t1 = timeit.Timer("create_list_with_concat(100)", "from __main__ import 
create_list_with_concat")
print("concat ",t1.timeit(number=1)*1000, "milliseconds")
t1 = timeit.Timer("create_list_with_concat(1000)", "from __main__ 
import create_list_with_concat")
print("concat ",t1.timeit(number=1)*1000, "milliseconds")
# OUTPUT
# concat  0.05283101927489042 milliseconds
# concat  2.8588240093085915 milliseconds

非常感谢帮忙.

Answer 1

时间复杂性不是 O(N)

两个列表A和B的concat操作的时间复杂度是O(A + B).这是因为您没有添加到一个列表,而是创建一个全新的列表并使用A和B中的元素填充它,要求您迭代这两个列表.

因此,执行操作l = l + [i]是O(len(l))让您N执行N操作的步骤,从而导致整体复杂性O(N^2)

您正在使用append或extend函数混淆concat ,它不会创建新列表但会添加到原始列表中.如果您使用这些功能,那么您的时间复杂度确实如此O(N)

另外一点:

符号l = l + [i]可能令人困惑,因为直觉上它似乎[i]只是被添加到现有的l.这不是真的!

l + [i]构建一个全新的列表,然后l指向该列表.

另一方面l += [i]修改原始列表并表现得像extend