时间戳

首页 > 解决方案 > 在 python 中使用 concat 运算符创建列表的复杂性

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

问题描述

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

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

这是我的思考过程：我知道 concat 运算符是O(k)要k添加到原始列表的列表的大小。由于我们一次添加一个字符列表，因此在这种情况下的大小k始终不变，因此 concat 操作会采取步骤。由于循环迭代次数，算法将执行步骤 -每次迭代执行步骤。因此，算法的时间复杂度为. 该算法的实际执行时间类似于执行连接所需的时间。对于这样的函数，我希望以下是正确的：当您将输入大小增加 10 倍时，输出（执行时间）将增加 10 倍，因为：11nn1O(n)T(n) = dnd

(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

非常感谢帮忙。

标签： pythonalgorithmdata-structurestime-complexity

解决方案

时间复杂度不O(N)

两个列表 A 和 B 的 concat 操作的时间复杂度为O(A + B). 这是因为您没有添加到一个列表中，而是创建了一个全新的列表并使用来自 A 和 B 的元素填充它，这需要您遍历这两个列表。

因此，做操作l = l + [i]是O(len(l))，给你留下N做操作的步骤N，导致整体的复杂性O(N^2)

您将 concat 与appendorextend函数混淆了，它不会创建新列表而是添加到原始列表中。如果你使用这些函数，你的时间复杂度确实是O(N)

附加说明：

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

l + [i]建立一个全新的列表，然后l指向该列表。

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

推荐阅读