时间复杂度如何dict.清除（）是python中的O（1）？

Question

根据https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt，时间复杂度dict.清除（）是O（1）。在

据我所知，dict.清除（）与分配dict={}不同，如dict.清除（）更改同一dict，dict={}创建新dict

现在如果dict.清除（）正在清除同一dict对象，然后如何在O（1）中完成它。在

Answer 1

它被称为O（1）的一些理由：

clear()方法实际上只是将内部字典结构分配给新的空值（如source所示）。看起来O（n）部分是引用计数和其他与GC相关的内容减少的结果。但这纯粹是CPython使用的GC方法的一个功能（即引用计数）；您可以设想不同的方法，这些方法不需要像这样显式的清理，或者清理会在很晚之后发生（甚至会逐渐消失）。由于理想情况下，clear()的时间复杂度不应依赖于底层的GC方法，因此省略了所有与GC相关的部分，使其成为“O（1）”。在我看来，这主要是一个定义上的争论，而不是其他任何东西，但这至少是一些正当理由。在

Answer 2

我首先认为dict.clear只是执行了一些引用减少，让垃圾回收器完成脏的非O（1）工作，但是看看source code（感谢timgeb提供了链接），似乎并不是这样：

   oldvalues = mp->ma_values;
    if (oldvalues == empty_values)
        return;
    /* Empty the dict... */
    dictkeys_incref(Py_EMPTY_KEYS);
    mp->ma_keys = Py_EMPTY_KEYS;
    mp->ma_values = empty_values;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    /* ...then clear the keys and values */
    if (oldvalues != NULL) {
        n = oldkeys->dk_nentries;
        for (i = 0; i < n; i++)
            Py_CLEAR(oldvalues[i]);

我看到的是，如果字典有值，那么会执行一个循环来减少对这些值的引用，并将指针设置为NULL。所以看起来O(n)不是{}，因为它取决于值的数目。在

当您分配给这样的新dict时，d = {}，这是O(1)，但是当不再被引用时，垃圾回收器必须删除旧对象。这在赋值时可能不正确，但除非python突然退出，否则会发生这种情况。在