Python List Reverse 的时间复杂度是多少？

Question

我看过这个页面 https://wiki.python.org/moin/TimeComplexity 但我没有看到列表中的 reverse() 函数。 list 的 reverse() --- 的时间复杂度是多少？

我的时间实验表明它是 O(n) 对于更大的尺寸。任何人都可以确认吗？

timeit 反转大小列表的时间

   10    .1027
  100    .2347
 1000    .6704
10000   6.204
20000  12.9

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

Answer 1

是的，你是对的，它是 O(n)，其中 n - 列表的长度。在这里查看更多信息： https ://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

原文由 Serenity 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果您 在这里查看 reverse 方法的实现，那么它看起来如下：

 static PyObject *
listreverse(PyListObject *self)
{
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
}

因此，该操作实际上委托给了 reverse_slice 。那么，让我们看看它：

 static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

因此，这里有 2 个索引最初设置在列表的开头和结尾。然后，在 while 循环的每次迭代中，交换各个索引处的元素：

 PyObject *t = *lo;
*lo = *hi;
*hi = t;

然后左边的索引递增，右边的索引递减：

 ++lo;
--hi;

只要右侧索引超过左侧索引，循环就会继续。因此，如果列表中有 n 元素，则将执行 n/2 迭代，因此时间复杂度为 O(n)

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