python - Python list 的 count() 函数的时间复杂度是多少？

Question

我正在尝试计算 count() 函数的时间复杂度。

例如，如果有一个 [1, 2, 2, 3] 的列表，并且使用 [1, 2, 2, 3].count(2) .

我无休止地搜索并查看了 Python wiki here ，但它不在那里。

我找到答案最接近的是 here ，但是复杂性字段恰好是空的...有人知道答案是什么吗？

Answer 1

深入了解 CPython 源代码并访问 Objects/listobject.c ，你会在那里找到 count() 方法的源代码。它看起来像这样:

static PyObject *
list_count(PyListObject *self, PyObject *value)
{
    Py_ssize_t count = 0;
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
        if (cmp > 0)
            count++;
        else if (cmp < 0)
            return NULL;
    }
    return PyLong_FromSsize_t(count);
}

它的作用是简单地遍历列表中的每个 PyObject，如果它们在丰富的比较中相等(请参阅 PEP 207)，则会递增一个计数器。该函数仅返回此计数器。

最终list_count的时间复杂度为O(n)。只要确保您的对象没有时间复杂度很高的 __eq__ 函数，您就安全了。