python - 在 python 列表中交换元素的时间复杂度

Question

如果我执行以下操作，在 python 列表中交换元素的时间复杂度是多少

案例 1:(惯用方式)交换列表中的两个元素

>>> a = [1, 2, 3, 4, 5]
>>> a[1], a[3] = a[3], a[1]  # Pythonic Swap --> x, y = y, x

>>> print(a)
[1, 4, 3, 2, 5]

问题1:交换步骤的时间复杂度是多少？ python 内部是做什么的。

案例 2:(非常低效的方式)交换列表中的两个元素

>>> a = [1, 2, 3, 4, 5]
>>> temp1, temp2 = a[1], a[3]
>>> del a[1]  # a = [1, 3, 4, 5]
>>> a.insert(1, temp2)  # a = [1, 4, 3, 4, 5]
>>> del a[3]  # a = [1, 4, 3, 5]
>>> a.insert(3, temp1)  # a = [1, 4, 3, 2, 5]
>>> print(a)
[1, 4, 3, 2, 5]

如果我这样做，每当我在任何索引处插入或删除时，该索引右侧的所有内存地址都需要分别向右或向左移动/复制一步。所以它需要 O(K)，其中 K 是我们插入或删除的索引右侧的地址数。如果我错了，请纠正我。

---

一些分析

如果列表非常小，那么运行时复杂度与我使用的任何方法(Case1 或 Case2)无关紧要。但是，如果列表非常大，如 a = [i for i in range(0,1000000)] 那么交换列表中两个元素的有效方法是什么？在这里，我使用百万记录列表交换索引 100 和 54321 对上述两种情况进行了一些基本分析，结果如下。令人惊讶的是，这两种情况的性能几乎相同。

a = [i for i in range(0,1000000)]

Case1 分析

$时间python3 case1_script.py

real    0m0.129s
user    0m0.088s
sys     0m0.041s

$ python3 -m cProfile case1_script.py

3 function calls in 0.060 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.047    0.047    0.060    0.060 list_ele_swap_profile.py:1(<module>)
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    1    0.013    0.013    0.013    0.013 {range}

Case2 分析

$时间python3 case2_script.py

real    0m0.132s
user    0m0.090s
sys     0m0.042s

$ python3 -m cProfile case2_script.py

5 function calls in 0.115 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.048    0.048    0.115    0.115 list_ele_swap_profile.py:1(<module>)
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     2    0.001    0.001    0.001    0.001 {method 'insert' of 'list' objects}
     1    0.066    0.066    0.066    0.066 {range}

问题 2:如果列表非常大，如上所示，交换列表中两个元素的有效方法是什么。

问题 3: 在思考这个问题时我还有一个疑问，那么如果从列表需要复制/移动内存地址，那么如何从列表中删除一个元素是 O(1)。

---

PS:我不认为这是一个重复的问题，我已经完成了以下问题，但没有一个是我要找的。我有兴趣了解上述操作的时间/空间复杂度。谢谢。

• Fastest way to swap elements in Python list
• Swapping elements in lists in python
• Swapping numbers in lists
• How does swapping of members in the python tuples (a,b)=(b,a) work internally?
• Is there a standardized method to swap two variables in Python?

Answer 1

答案取决于您对 python 的实现。 我假设您对默认的 CPython 实现感兴趣。 从现在开始，我说“python”而不是“cpython”。

Python 中的列表或多或少像 C 中的数组一样适合您的目的。

删除其中的一个元素需要移动它上面的所有元素，插入也是如此，因此这两个操作是 O(i)，其中 i 是您删除/插入的项目之后的项目数。 您的第一个答案是 O(1)，这样更好。

你的分析是错误的，因为这个数组的大小实际上很小，而且你的时间安排也考虑了构建数组的时间。 尝试以下实验:构建一次大小为 100000 的数组，并尝试交换其中的两个元素 100000 次。 您会看到第一个代码比第二个代码至少快 100 倍(这是我在计算机上获得的数字)，这当然是交换 python 列表中元素的好方法。