Python 内置函数的时间复杂度？

Question

有没有什么好的参考资源可以了解Python内置函数（如 , ）的时间复杂dict.fromkeys()度.lower()？我找到了像UCI 资源这样的链接，其中列出了基本列表和集合操作的时间复杂度，但当然，并非所有内置操作都列出了时间复杂度。我还找到了 Python Reference - The Right Way，但大多数参考文献都有#TODO 以表示时间复杂度。

我也尝试阅读Python内置函数的源代码来弄清楚这些功能是如何dict.fromkeys()实现的，但感觉很失落。

Answer 1

这是一个很好的起点：

https://wiki.python.org/moin/TimeComplexity

它表示获取项目的时间复杂度为 O(1)，迭代的时间复杂度为 O(n)（平均情况）。那么，如果.fromkeys()你只迭代字典的键，然后将它们作为新字典的键，同时还设置值，我认为你会在 O(n) 和 O(2n) 之间，其中 n 是第一个字典中键的数量。

抱歉，我只能提供猜测，但希望该链接对您有所帮助。