面试题：C++中vector基于值查询的时间复杂度分析

Question

在C++中，vector是常用的容器。假设我们要在一个vector<int>中通过值进行查找，编写一个函数实现该查找功能，并分析其时间复杂度。请说明你的分析过程。

Answer 1

#include <vector>
#include <iostream>

// 查找函数
bool findValueInVector(const std::vector<int>& vec, int target) {
    for (int num : vec) {
        if (num == target) {
            return true;
        }
    }
    return false;
}

1. 时间复杂度分析：
   • 该函数使用了一个for循环遍历vector。在最坏的情况下，需要遍历vector中的每一个元素才能确定目标值是否存在。
   • 假设vector的大小为n，循环会执行n次。因此，时间复杂度为$O(n)$。其中，$O$表示渐进时间复杂度，$n$是vector中元素的数量。在平均情况下，也需要遍历大约一半的元素，时间复杂度同样为$O(n)$。