Python

Question

考虑以下 bubble sort 程序：

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 变量进行排序，这意味着 space 复杂度为 0(1)。但我的理解是，元组交换只是将标识符重新分配给对象（link）。这需要任何额外的 space 吗？这里的 space 复杂度是多少？还是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)，因为元组可以在执行交换后立即释放。

唯一使用的额外内存是用于保存要交换的值的堆栈 space（这甚至可能不是任何额外的东西，因为没有交换的最大堆栈深度可能已经足够了）。然后，ROT_TWO 操作码执行交换：

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

请注意，不需要使用额外的内存；顶部的两个堆栈元素只是交换。 top 和 second 以上作为临时变量。

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

Python - What is the space complexity when tuple swap is used in bubble sorting?

tuples

swap

bubble-sort

space-complexity