面试题：C++中vector随机访问时间复杂度相关代码分析

Question

请分析以下C++代码中，访问vector元素的时间复杂度，并说明原因。 ```cpp #include <iostream> #include <vector> int main() { std::vector<int> vec(1000); for (size_t i = 0; i < vec.size(); ++i) { vec[i] = i; } int value = vec[500]; return 0; } ```

Answer 1

1. 时间复杂度分析：

   • 对于 for 循环部分，循环次数为 vec.size()，即1000次。每次循环执行 vec[i] = i，这里访问 vec[i] 操作的时间复杂度为 $O(1)$，因为 vector 内部采用连续内存存储元素，通过索引直接访问元素的时间是固定的。所以整个 for 循环的时间复杂度为 $O(n)$，其中 $n = vec.size() = 1000$。
   • 对于 int value = vec[500]; 这一行，同样是通过索引访问 vector 中的元素，由于 vector 是连续内存存储，通过索引直接访问的时间复杂度为 $O(1)$。

2. 综合分析：

   • 整个代码中访问 vector 元素（包含 for 循环中的访问和单独的 vec[500] 访问），主要的时间消耗在 for 循环部分，其时间复杂度为 $O(n)$。所以从访问 vector 元素的角度看，整体时间复杂度为 $O(n)$。

   • 原因是：vector 内部实现是基于数组，在连续内存空间存储元素。通过索引 [] 操作符访问元素时，根据索引值直接计算内存地址并获取元素，这个过程不依赖于元素个数 $n$，时间消耗是固定的，为 $O(1)$。但由于有一个循环遍历了 vector 的所有元素，所以整体访问 vector 元素的时间复杂度由这个循环主导，为 $O(n)$。