是否arr = [val] * N具有班輪或恆定時間？

我正在努力解決一些編碼問題。我想知道answ = [max] * N是線性還是恆定時間？是否arr = [val] * N具有班輪或恆定時間？

def solution(N, A): 

    answ = [0] * N 
    max = 0 

    for item in A: 
     if item > N: 
      answ = [max] * N # this line here. Linear or constant time ? 
     else: 
      answ[item-1] += 1 

      if answ[item-1] > max: 
       max = answ[item-1] 

    return answ

列表A具有長度M. 所以，如果時間是恆定的，我將接收算法的O（M）的複雜性。如果線性，我將接收O（M * N）複雜度。

來源

2016-06-21 Eduard Bondarenko

分配'寫回信= [0 ] * N'在N中是線性的。它怎麼會不是？您正在創建一個長度爲N的列表。每個元素都必須設置爲0.無法在常量時間內創建列表。 –

您可以使用'collections.defaultdict（lambda max = max：max）'來代替默認爲'max'的字典。它將按平均每次操作分攤的O（1）計算。 – interjay

除了列表乘法創建對同一個*對象的多個引用。我不知道整數會發生什麼，當然你需要創建'N'引用，但它原則上不是*和創建數組中任何元素的N個拷貝一樣。 – alexis

是的。 CPython列表僅僅是指針數組。檢查出的結構定義在listobject.h：

https://hg.python.org/cpython/file/tip/Include/listobject.h#l22

typedef struct { 
    PyObject_VAR_HEAD 
    /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ 
    PyObject **ob_item; 

    /* ob_item contains space for 'allocated' elements. The number 
    * currently in use is ob_size. 
    * Invariants: 
    *  0 <= ob_size <= allocated 
    *  len(list) == ob_size 
    *  ob_item == NULL implies ob_size == allocated == 0 
    * list.sort() temporarily sets allocated to -1 to detect mutations. 
    * 
    * Items must normally not be NULL, except during construction when 
    * the list is not yet visible outside the function that builds it. 
    */ 
    Py_ssize_t allocated; 
} PyListObject;

如果不說服你....

In [1]: import time 

In [2]: import matplotlib.pyplot as plt 

In [3]: def build_list(N): 
    ...:  start = time.time() 
    ...:  lst = [0]*N 
    ...:  stop = time.time() 
    ...:  return stop - start 
    ...: 

In [4]: x = list(range(0,1000000, 10000)) 

In [5]: y = [build_list(n) for n in x] 

In [6]: plt.scatter(x, y) 
Out[6]: <matplotlib.collections.PathCollection at 0x7f2d0cae7438> 

In [7]: plt.show()

來源

2016-06-21 09:32:34

由於您正在使用值max填充大小爲N的數組，因此這意味着您正在執行N寫入 - 因此它的複雜性是線性的。

有一些數據結構可以接收所有未使用值顯式聲明的項目的綁定數組大小的「默認」值。但是，Python的list（）不是這樣的結構。

來源

2016-06-21 09:02:41 advance512

是否arr = [val] * N具有班輪或恆定時間？

回答

相關問題