Python list的count（）函数的时间复杂度是多少？ [英] What is the time complexity of Python list's count() function?

问题描述

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

I'm trying to figure what the time complexity of the count() function.

例如，如果存在 [1 ，2、2、3] 和 [1、2、2、3] .count（2）。

我已经无休止地搜索并查看了Python Wiki 此处，但不存在。

I've searched endlessly and looked at the Python wiki here, but its not there.

我最近找到答案的是此处，但复杂性字段恰好为空...答案是谁吗？

The closest I've come to finding an answer is here, but the field for complexity happens to be empty... Does anyone what the answer is?

推荐答案

挖掘到CPython源代码并访问 Objects / listobject.c ，您将找到 count（ ）方法。看起来像这样：

Dig into the CPython source code and visit Objects/listobject.c, you will find the source code for the count() method in there. It looks like this:

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 ），则计数器增加。该函数只返回此计数器。

What it does is to simply iterate over every PyObject in the list, and if they are equal in rich comparision (see PEP 207), a counter is incremented. The function simply returns this counter.

最后， list_count 的时间复杂度为O（n）。只要确保您的对象不具有时间复杂度大的 __ eq __ 函数，您就可以安全使用。

In the end, the time complexity of list_count is O(n). Just make sure that your objects don't have __eq__ functions with large time complexities and you'll be safe.

这篇关于Python list的count（）函数的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！