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

Question

我试图计算count()函数的时间复杂度.

如果有列表[1, 2, 2, 3]并且[1, 2, 2, 3].count(2)被使用,则为Ex .

我无休止地搜索并在这里查看了Python维基,但它不在那里.

我最接近找到答案就在这里,但复杂的领域恰好是空的......有人的答案是什么？

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__大时间复杂性的功能,您就会安全.

Answer 2

由于该count方法必须检查列表中的每个条目，因此运行时间将为 O(n)。