时间复杂度如何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

我首先认为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突然退出，否则会发生这种情况。在