array[::-1] 的时间复杂度和空间复杂度是多少 [英] What is the time complexity and space complexity of array[::-1]

问题描述

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

When reverse a list in Python, I usually use the array[::-1] for reversing and I know that a more common way might swap from two sides of the list. But I'm not sure the difference between these two solutions such as time complexity and space complexity.

下面这两种方法的代码:

Code for this two methods below:

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

推荐答案

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

In C python, assuming array is a list, the expression array[::-1] triggers the following algorithm found in function list_subscript() in the source file 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是列表的长度.当然，这里没有惊喜.

Both time and space complexity of this piece of code are O(n) where n is the length of the list. Of course there is no suprise here.

你的函数reverse()也有O(n)时间复杂度，不同的是它不使用临时列表.

Your function reverse() has also O(n) time complexity, the difference is that it does not use a temporary list.

内置的 C 函数比纯 python 循环快得多(在我的电脑上，对于 100 个元素的列表，大约是 10 倍).

The built-in C function is much faster than the pure python loop (about 10 times on my computer for a 100 elements list).

这篇关于array[::-1] 的时间复杂度和空间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！