C++多维vector执行v[i]=v[j]操作的时间复杂度为O(1)还是线性？

明确结论 #

该操作的时间复杂度分两种场景，不能一概而论：

• 默认拷贝赋值场景：线性时间复杂度
• C++11及以上的移动赋值场景：常数时间复杂度，也就是你提到的算法博客里的适用场景

具体原因拆解 #

1. []操作符的复杂度确认 #

和你查阅的资料一致，不管vector是多少维度，[]运算符仅做地址偏移计算、返回对应位置元素的引用，这一步的时间复杂度固定为O(1)，不会影响整个赋值操作的复杂度量级。

2. 赋值操作的复杂度差异核心 #

整个表达式的复杂度由vector的=运算符逻辑决定：

• 拷贝赋值（默认行为）
  标准库vector的拷贝赋值需要遍历右值vector的所有元素，逐份拷贝到左值vector的内存空间中，还要额外处理容量扩容、原有元素析构的逻辑，时间复杂度和右值vector存储的元素数量成线性关系，也就是参考页标注的线性复杂度。你写的v[i] = v[j]默认走的就是这个逻辑，复杂度为O(k)，k是v[j]存储的元素总数。
• 移动赋值（特殊场景）
  C++11版本之后引入了移动语义，当赋值的右值是临时对象，或者你显式通过std::move将右值转为右值引用时，vector的赋值不会做元素拷贝，只会交换两个vector内部的三个底层指针（数据起始指针、已用空间末尾指针、容量末尾指针），整个操作只涉及数次固定的指针赋值，时间复杂度为O(1)。
  你提到的算法博客里的说法就是基于这个场景，这类竞赛算法通常会显式使用移动赋值来优化复杂度，而且会默认放弃赋值后原v[j]的使用权（移动操作后原vector会处于有效但未定义的状态，一般不能再读取使用）。

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