python 中 dict.clear() 的时间复杂度是 O(1) 吗？

Question

根据https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt，dict.clear ()的时间复杂度为O(1)。

据我所知， dict.clear() 与分配 dict = {} 不同，因为 dict.clear() 对同一个字典进行更改，而 dict = {} 创建一个新的字典。

现在，如果 dict.clear() 正在清除同一个 dict 对象，那么它如何在 O(1) 内完成它。

Answer 1

为什么它被称为 O(1) 的一些基本原理：

该方法实际上只是将内部字典结构分配给新的空值（如源代码clear()中所示）。看似 O(n) 的部分是减少引用计数和其他 GC 相关内容的结果。但这纯粹是 CPython 使用的 GC 方法（即引用计数）的功能；您可以设想不同的方法，这些方法不需要像这样的显式清理，或者清理会在很晚之后发生（甚至被摊销）。由于理想情况下 的时间复杂度不应该取决于底层 GC 方法，因此所有与 GC 相关的部分都被省略，使其成为“O(1)”。在我看来，这主要是一个定义性的论点，但这至少是一些理由。clear()