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

Question

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

这两种方法的代码如下：

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

在Cpython中，假设数组是一个列表，表达式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;
}

这段代码的时间和 space 复杂度都是 O(n)，其中 n 是列表的长度。当然这里没有惊喜。

你的函数reverse()也有O(n)时间复杂度，区别在于它不使用临时列表。

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

Answer 2

我运行在 Jupyter 上使用 %%timeit 进行实验，数组大小为 100、1000 和 10000。array[::-1] 和 reverse(array)（从两个交换列表的末尾）几乎呈线性增长。然而，Python 内置的 reversed 函数所花费的时间几乎保持不变，所以我想这将是最好的选择。

Time Comparison

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

What is the time complexity and space complexity of array[::-1]

python

time-complexity

space-complexity