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

Question

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

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

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

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

Answer 1

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

Answer 2

它需要需要访问所有元素才能知道是否对它们进行计数。没有理由让它做更多的工作。

因此，它不可能比 O(n) 更好，并且由于即使是最基本、最简单、最直接的实现也是 O(n)，您实际上需要非常愚蠢或非常恶意才能实现再慢一点。

因此，根据常识，最坏情况下的步骤复杂度很可能是 O(n)。

Answer 3

深入了解 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），则计数器递增。该函数只是returns这个计数器。

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

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

What is the time complexity of Python list's count() function?

python

complexity-theory

time-complexity

python-3.x