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

由于您使用值 max 填充大小为 N 的数组，这意味着您正在执行 N 写入 - 因此它的复杂性是线性的。

有些数据结构可以接收 "default" 值，用于所有未明确声明为绑定数组大小的项。但是，Python 的 list() 不是这样的结构。

Answer 2

是的。 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()

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

Does arr = [val] * N have liner or constant time?

python

algorithm

asymptotic-complexity