python - arr = [val] * N 是否具有线性或常数时间？

Question

我正试图在 codility 解决一些问题。 我想知道 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 的长度为 M。 所以，如果时间是常数，我将得到 O(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()