交换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)]

案例1分析

$ time 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}

案例2分析

$ time 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:我认为这不是一个重复的问题,我已经完成了以下问题,但没有一个问题符合我的要求.我有兴趣了解上述操作的时间/空间复杂性.谢谢.

• 在Python列表中交换元素的最快方法
• 交换python中列表中的元素
• 在列表中交换数字
• 如何交换python元组中的成员(a,b)=(b,a)在内部工作？
• 是否有标准化的方法在Python中交换两个变量？

Answer 1

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

python 中的列表或多或少可以满足您的目的，就像 C 中的数组一样。

删除其中的元素需要移动其上方的所有元素，插入也是如此，因此这两个操作的时间复杂度为 O(i)，其中 i 是您删除/插入的项目之后的项目数。你的第一个答案是 O(1)，所以更好。

您的分析是错误的，因为这个数组的大小实际上非常小，并且您的计时还考虑了构建数组的时间。尝试以下实验：构建一个大小为 100000 的数组一次，并尝试交换其中两个元素 100000 次。你会发现第一个代码比第二个代码至少快 100 倍（这是我在计算机上获得的数据），这当然是交换 python 列表中元素的好方法。