What is the time complexity of Python list's c

问题:

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

Ex if there is a list of [1, 2, 2, 3] and [1, 2, 2, 3].count(2) is used.

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?

回答1:

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);
}

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.

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.

回答2:

Because the count method has to check every entry in the list, the runtime is going to be O(n).

回答3:

It needs needs to visit all elements in order to know whether to count them or not. There is no reason for it to do any more work than that.

So, it cannot possibly be better than O(n), and since even the most basic, simple, straightforward implementation is O(n), you would need to actually be either very stupid or very malicious to make it any slower.

Ergo, by common sense, the worst-case step complexity is most likely O(n).