在Python中使用 [::-1] 来反转列表，是否具有 O(1) 的空间复杂度？

Question

如果我写了这样的代码：

item_list = item_list[::-1]

这样做的空间复杂度是否为O(1)？我认为item_list[::-1]会创建一个新列表，因此可能是O(n)。在Python中，使用item_list.reverse()才是以O(1)空间反转的正确方法吗？

- GoBlueDev

---

不，它会创建一个列表的副本，并需要线性的空间/时间。 - juanpa.arrivillaga

我认为reversed()的时间复杂度将会是O(1)。 - Olvin Roght

@Olvin 当然可以，但如果你把它列成列表就不行了。 - juanpa.arrivillaga

@OlvinRoght：这是一个生成器。如果你在它上面使用list(..)，那么你会复制一份，因此需要*O(n)*的空间。 - Willem Van Onsem

@WillemVanOnsem 的术语细节，它返回一个迭代器，而不是生成器。 - juanpa.arrivillaga

Answer 1

您说得对，some_list[::-1]会创建一个新列表，该列表将有n个“插槽”，因此需要O(n)内存。

此外，在Python解释器CPython中，.reverse()方法的内存使用是O(1)。实际上，如果我们查看reverse方法的源代码 [GitHub]，我们可以看到：

/*[clinic input]
list.reverse
Reverse *IN PLACE*.
[clinic start generated code]*/

static PyObject *
list_reverse_impl(PyListObject *self)
/*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
{
    if (Py_SIZE(self) > 1)
        <b>reverse_slice(</b>self->ob_item, self->ob_item + Py_SIZE(self)<b>)</b>;
    Py_RETURN_NONE;
}

因此，它调用一个名为reverse_slice的函数，这个函数的实现在[Github]中:

/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

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

因此，它使用两个指针，一个按升序迭代，一个按降序迭代，并且这些指针将值相互“交换”，直到它们相遇在中间。

- Willem Van Onsem