什么是阵列的时间复杂度和空间复杂度[:: - 1]

当在Python中反转列表时，我通常使用数组[： - 1]进行反转，并且我知道更常见的方法可能会从名单的两面。但我不确定这两种解决方案之间的区别，如时间复杂性和空间复杂性。什么是阵列的时间复杂度和空间复杂度[:: - 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

来源

2017-07-26 JoshuaW1990

除了主题外，您还可以使用['reversed（）']（https://docs.python.org/2/library/functions.html#reversed）内置函数而不是'[:: - 1 ]'遍历反向列表。 –

您可以使用['timeit']（https://docs.python.org/2/library/timeit.html）测试哪种方法更快，您可以使用['dis']（https：// docs。 python.org/2/library/dis.html）模块来查看你所做的每个函数的字节码。作为一个经验法则，可以使用'array [:: -1]'或'list（reversed（array））'来反转数组而不是自定义函数。由于内置函数使用CPython实现，因此非常优化。你可以在这里找到源代码：[github内置函数CPython]（https://github.com/python/cpython） –

谢谢。也许我没有解释得很清楚。是的，我可以使用'reverse'函数来反转列表，但有时我还需要反转类似字符串的内容，而'reverse'函数不适用于字符串。在这种情况下，我通常使用'string [:: - 1]'，但我不知道它是如何工作的，它的性能如何。 – JoshuaW1990

在C蟒，假定阵列是一个列表，该表达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倍）。

来源

2017-07-26 15:00:48 Gribouillis

什么是阵列的时间复杂度和空间复杂度[:: - 1]

回答

相关问题