什麼是陣列的時間複雜度和空間複雜度[:: - 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]

回答

相關問題