7

我想知道使用 append() 构建的 Python v2.7 列表的复杂性顺序是什么？Python列表是双向链接的，因此它是恒定的复杂性，还是单链接的，因此是线性复杂性？如果它是单链接的，我如何在线性时间内从迭代中建立一个列表，该列表按从头到尾的顺序提供列表的值？

例如：

def holes_between(intervals):
  # Compute the holes between the intervals, for example:
  #     given the table: ([ 8,  9] [14, 18] [19, 20] [23, 32] [34, 49])
  #   compute the holes: ([10, 13] [21, 22] [33, 33])
  prec = intervals[0][1] + 1 # Bootstrap the iteration
  holes = []
  for low, high in intervals[1:]:
    if prec <= low - 1:
      holes.append((prec, low - 1))
    prec = high + 1
  return holes
4

1 回答 1

23

python的时间复杂度list.append()是O(1)。请参阅Python Wiki 上的时间复杂度列表。

在内部，python 列表是指针向量：

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;

向量根据ob_item需要通过过度分配调整大小，以提供附加的摊销 O(1) 成本：

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

这使得 Python 列出了动态数组。

于 2013-02-27T20:39:48.540 回答