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

Question

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

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

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

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

原文由 SW Williams 发布，翻译遵循 CC BY-SA 4.0 许可协议

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__ 时间复杂度高的函数，你就安全了。

原文由 Berk Özbalcı 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

原文由 g.d.d.c 发布，翻译遵循 CC BY-SA 3.0 许可协议