您好, 欢迎来到 !    登录 | 注册 | | 设为首页 | 收藏本站

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

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

探究cpython源代码并访问Objects/listobject.c,您将在其中找到该@H_301_1@count()方法的源代码。看起来像这样:

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

它的作用是简单地遍历@H_301_1@PyObject列表中的每一个,如果它们的丰富比较相等(请参阅PEP 207),则将增加一个计数器。该函数仅返回该计数器。

最后,时间复杂度@H_301_1@list_count为O(n)。只要确保您的对象不具有@H_301_1@__eq__时间复杂度高的功能,您就可以安全。

python 2022/1/1 18:40:56 有270人围观

撰写回答


你尚未登录,登录后可以

和开发者交流问题的细节

关注并接收问题和回答的更新提醒

参与内容的编辑和改进,让解决方法与时俱进

请先登录

推荐问题


联系我
置顶