Python - 在冒泡排序中使用元组交换时的空间复杂度是多少？

Question

考虑以下冒泡排序程序:

arr = map(int, raw_input().split(' '))
print "Unsorted: \n{arr_name}".format(arr_name = arr)

for j in range(len(arr) - 1, 0, -1):
    for i in range(j):
        if (arr[i] > arr[i + 1]):
            arr[i], arr[i + 1] = arr[i +1], arr[i]

print "Sorted: \n{arr_name}".format(arr_name = arr)

通常使用 temp 变量进行排序，这意味着空间复杂度为 0(1)。但我的理解是，元组交换只是将标识符重新分配给对象( link )。这需要额外的空间吗？这里的空间复杂度是多少？由于创建了元组，它仍然是 O(1) 吗？

Answer 1

实际上，交换得到了优化(至少在 CPython 中)，因此不会创建元组:

>>> def f():
...     a,b = b,a
... 
>>> dis(f)
  2           0 LOAD_FAST                0 (b)
              3 LOAD_FAST                1 (a)
              6 ROT_TWO             
              7 STORE_FAST               1 (a)
             10 STORE_FAST               0 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE 

仍然是 O(1)，是的。即使创建了一个元组，它仍然是 O(1)，因为元组可以在执行交换后立即释放。

唯一使用的额外内存是用于保存要交换的值的堆栈空间(甚至可能没有任何额外的内存，因为没有交换的最大堆栈深度可能已经足够了)。然后，ROT_TWO操作码执行交换:

    TARGET(ROT_TWO) {
        PyObject *top = TOP();
        PyObject *second = SECOND();
        SET_TOP(second);
        SET_SECOND(top);
        FAST_DISPATCH();
    }

请注意，不需要使用额外的内存；顶部的两个堆栈元素被简单地交换。上面的 top 和 second 充当临时变量。