时间和 space 复杂度比较：通过循环或 dict(zip(s, t)) 将两个列表的元素添加到一个字典中

Question

我是 python 的新手，正在尝试弄清楚时间和 space 复杂性的概念。我想对两个长度相同的列表进行 dict。我可以通过以下两种方式做到这一点：

1) 通过遍历列表并将它们添加到字典中：

 dictLists = {}
        for i in range(0,len(list1)):
            dictLists[list1[i]] = list2[i]

2) 通过压缩列表，然后从中生成字典：

       dictZip = dict(zip(list1,list2))

据我了解，第一种方法的时间复杂度应该是 O(N)，其中 N 是列表的长度。但是，我不知道第二个选项的时间复杂度，除了 zip 操作本身需要 O(1) 时间复杂度这一事实。

这两种方法的时间复杂度有什么不同？由于额外的 zip 对象，第二种方法会不会有额外的 space 复杂性？

Answer 1

两者具有相同的时间和 space 复杂度。他们每个人都有自己的开销，在谈论复杂性时不包括在内，比如你提到的 zip 对象和你没有提到的 range 对象，所有在阴影中发生的函数调用...... .

在实践中，这些并不重要，所以不要过早地进行微优化（“过早地”在这里是指没有充分的理由预期会出现性能问题，没有遇到性能问题，也没有进行基准测试）——选择dict(zip(list1, list2)).

的可读选项

P.S.

except the fact that the zip operation itself takes O(1) time complexity

创建一个 zip 是 O(1)，但遍历它的所有元素是 O(N) 的元素数量。

Answer 2

由于 python 是一种动态解释型语言，需要在运行时间内弄清楚变量的类型，因此您实现代码的方式的一些变化在运行时间。例如，在第一个解决方案中，python 需要在每次迭代中找出 "i" 的类型（可以使用 cython 修复），因此这会减慢程序速度。话虽如此，您可能不会注意到少量迭代。正如您在测试平台中看到的那样，第一种方法几乎慢了 4 倍。

import time
list1 = [x for x in range(1000000)]
list2 = [x for x in range(1000000)]

dictLists = dict()
l = len(list1)

s = time.time()
for i in range(0, l):
    dictLists[list1[i]] = list2[i]
print(f"Time: {time.time()-s}")
# 0.39275574684143066

dictLists = dict()
s = time.time()

dictZip = dict(zip(list1,list2))
print(f"Time: {time.time()-s}")
# 0.09296393394470215

时间和 space 复杂度比较：通过循环或 dict(zip(s, t)) 将两个列表的元素添加到一个字典中

time and space complexity comparison: adding elements of two lists to a dict through loop or dict(zip(s, t))

python

time

complexity-theory

dictionary

time-complexity