在Python中合并两个列表的运行时

Question

假设我们有两个列表A = [a1, a2, ..., an](n个元素)和B = [b1, b2, ..., bm](m个元素),我们在Python中使用"+"将两个列表合并为一个,所以

C = A + B;

我的问题是这个操作的运行时是什么？我的第一个猜测是O(n+m),不确定Python是否比这更聪明.

Answer 1

当您使用两个列表连接时A + B,您将在内存中创建一个全新的列表.这意味着你的猜测是正确的:复杂性是O(n + m)(在哪里n和m是列表的长度),因为Python必须依次遍历两个列表来构建新列表.

您可以在Python列表list_concat的源代码中的函数中看到这种情况:

static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
/* ...code snipped... */
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {     /* walking list a */
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {     /* walking list b */
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
/* ...code snipped... */

如果你不需要在内存中有一个新的列表,那么利用列表是可变的这一事实通常是一个好主意(这就是Python 很聪明的地方).使用A.extend(B)的O(m)复杂性意味着您避免复制列表的开销a.

各种列表操作的复杂性列在这里对Python的维基.