arr = [val] * Nには、ライナーまたは一定の時間がありますか？

Question

私はコーディネートでいくつかの問題を解決しようとしています。 answ = [max] * 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は、時間が一定であれば、私は、アルゴリズムのO（M）の複雑さを受け取ることになります、だから、長M. を持っています。 線形の場合、私はO（M * N）の複雑さを受け取ります。

Answer 1

はい。 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() 

Answer 2

Nというサイズの配列に値maxを設定しているので、Nの書き込みが行われていることを意味します。したがって、複雑さは直線的です。

バインドされた配列サイズで明示的に値で宣言されていないすべての項目に対して「デフォルト」値を受け取ることができるデータ構造がいくつかあります。しかし、Pythonのlist（）はそのような構造体ではありません。