当在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
在 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 倍)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)