Python list.clear（）时间和空间复杂度？

Question

我正在写有关Python list.clear()方法的博客文章，在此我还想提及底层算法的时间和空间复杂性。我期望时间复杂度为O（N），遍历元素并释放内存？但是，我发现了一个article，实际上它是O（1）操作。然后，我在CPython实现中搜索了该方法的源代码，找到了一个我认为是list.clear()的实际内部实现的方法，但是，我不确定它是不是。这是该方法的源代码：

static int
_list_clear(PyListObject *a)
{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
         /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
           Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there is no guarantee that the list is actually empty
       at this point, because XDECREF may have populated it again! */
    return 0;
}

我可能是错的，但对我来说确实像O（N）。另外，我发现了类似的问题here，但那里没有明确的答案。只是想确认list.clear()的实际时间和空间复杂度，也许还需要一些解释来支持答案。任何帮助表示赞赏。谢谢。

Answer 1

是O（1）忽略了内存管理。说内存管理是O（N）不太正确，因为内存管理很复杂。

在大多数情况下，大多数时候，我们将内存管理的成本与触发它的操作的成本分开对待。否则，您几乎可以做的所有事情都会变成O（甚至不知道），因为几乎任何操作都可能触发垃圾回收过程或昂贵的析构函数或其他操作。哎呀，即使在具有“手动”内存管理功能的C语言中，也无法保证任何特定的malloc或free调用都会很快。

有一个论点，即对引用计数操作应区别对待。毕竟，list.clear显式地执行许多与列表长度相等的Py_XDECREF操作，即使结果没有对象的释放或最终确定，重新引用本身也将花费与列表长度成比例的时间。 >

如果计算Py_XDECREF操作，则list.clear显式执行，但是忽略可能由引用计数操作触发的任何析构函数或其他代码，并且假设PyMem_FREE是恒定时间，则list.clear为O（N ），其中N是列表的原始长度。如果您减去所有内存管理开销，包括显式Py_XDECREF操作，则list.clear为O（1）。如果将所有内存管理成本都算在内，则list.clear的运行时不会受到列表长度的任何函数的渐近限制。

Answer 2

您正确注意到，list.clear的CPython

Answer 3

快速time检查表明它是O（1）