python - 时间和空间复杂度比较 : adding elements of two lists to a dict through loop or dict(zip(s, t))

Question

我是Python新手，正在尝试弄清楚时间和空间复杂度的概念。我想制作两个列表的字典，两个列表的长度相同。我可以通过以下两种方式做到这一点:

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 对象，第二种方法会增加空间复杂度吗？

Answer 1

两者具有相同的时间和空间复杂度。它们各自都有自己的开销，在讨论复杂性时不包括这些开销，例如您提到的 zip 对象和您没有提到的 range 对象，以及所有函数调用发生在阴影中的事情......

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

<小时/>

附注

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

创建 zip 的时间复杂度为 O(1)，但迭代其所有元素的时间复杂度为 O(N)(就元素数量而言)。