Python list的count（）函数的时间复杂度是多少？

Question

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

例如，如果使用[1, 2, 2, 3]和的列表[1, 2, 2, 3].count(2)。

我已经无休止地搜索，并在这里查看了Python Wiki
，但那里没有。

我最想找到答案的地方是这里，但是复杂性领域恰好是空的……答案是谁吗？

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__时间复杂度高的功能，您就可以安全。