Python中列表元素交换的时间成本：这段代码总复杂度是否为O(n)？

1. 单次列表元素交换的时间成本 #

在Python中，nums[i], nums[j] = nums[j], nums[i]这种交换操作的时间复杂度是O(1)（常数时间）。

背后的逻辑很直观：

• 首先会把右侧的nums[j]和nums[i]打包成一个临时元组（这一步是固定开销，和元素类型、大小无关）
• 接着把元组里的两个值分别解包赋值给nums[i]和nums[j]
• 而列表通过索引访问元素本身就是O(1)的操作，所以整个交换过程不会随着列表规模变大而增加时间开销，属于纯粹的常数级操作。

2. 你的反转列表代码的总时间复杂度 #

先把你给出的代码再贴一下方便参考：

# nums = a list with n variables
i = 0
j = len(nums) - 1
while i < j:
    nums[i], nums[j] = nums[j], nums[i]
    i += 1
    j -= 1

这段代码是在原地反转列表，循环的执行次数是floor(n/2)次——比如n是偶数时执行n/2次，n是奇数时执行(n-1)/2次。不管哪种情况，循环次数都和列表长度n成线性关系。

因为每次循环里的所有操作（交换元素、i和j的自增自减）都是O(1)的常数操作，所以总时间复杂度就是O(n)，你的判断完全正确。

额外提一句：Python内置的nums.reverse()方法或者切片写法nums[::-1]（后者会返回新列表），时间复杂度同样是O(n)，不过内置方法是用C实现的，实际运行效率会比你手写的Python循环更高，但时间复杂度的量级是一致的。

内容的提问来源于stack exchange，提问作者louis770