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

Question

我已经看过这个页面 https://wiki.python.org/moin/TimeComplexity 但我没有在列表中看到相反的功能.列表反转的时间复杂度是多少？

我的时间实验表明,对于较大的尺寸,它是O(n).任何人都可以证实吗？

timeit反转大小列表的时间

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

Answer 1

如果您查看此处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)

Answer 2

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