array[::-1] 的时间复杂度和空间复杂度是多少

Question

当在Python中反转列表时，我通常使用数组[::-1]进行反转，并且我知道更常见的方法可能是从列表的两侧进行交换。但我不确定这两种解决方案之间的区别，例如时间复杂度和空间复杂度。

这两种方法的代码如下：

def reverse(array):
    array[:] = array[::-1]


def reverse(array):
    start, end = 0, len(array)-1
    while start < end:
        array[start], array[end] = array[end], array[start]
        start += 1
        end -= 1

Answer 1

在C python中，假设数组是一个列表，则表达式触发在源文件中的array[::-1]函数中找到的以下算法list_subscript()listobject.c

result = PyList_New(slicelength);
if (!result) return NULL;

src = self->ob_item;
dest = ((PyListObject *)result)->ob_item;
for (cur = start, i = 0; i < slicelength;
     cur += (size_t)step, i++) {
    it = src[cur];
    Py_INCREF(it);
    dest[i] = it;
}

这段代码的时间和空间复杂度都是O(n)其中n是列表的长度。当然，这并不奇怪。

您的函数reverse()也具有O(n)时间复杂度，不同之处在于它不使用临时列表。

内置的 C 函数比纯 python 循环快得多（在我的计算机上，对于 100 个元素的列表，大约快 10 倍）。