C++中求vector元素最值的时间复杂度分析是否正确？

首先贴出对应的代码：

#include <iostream>
using namespace std;
#include <vector>

int main()
{
    unsigned int n;
    cin >> n;
    int elementsOfVector;
    vector <double> wektor;
    for(int i = 0; i<n; i++) {
        cin >> elementsOfVector;
        wektor.push_back(elementsOfVector);
    }
    double min = wektor[0];
    double max = wektor[1];
    if (min > max) {
        min = wektor[1];
        max = wektor[0];
    }
        for(int i = 2; i<n; i++)    {
            if (max < wektor[i]) {
                max = wektor[i];
            }
            else if (min > wektor[i]) {
                min = wektor[i];
            }
        }
    cout << "Min " << min << " max " << max;
    return 0;
}

你的分析完全正确，补充几个细节帮你巩固理解：

• 第一个for循环执行n次，vector的push_back操作是**均摊O(1)**时间复杂度，所以这个循环整体是O(n)。
• 那段比较min和max的if语句是固定次数的操作，属于O(1)，这类常数时间操作在大O表示法中会被忽略。
• 第二个for循环执行n-2次，当n趋近于无穷大时，n-2和n的量级等价，所以也是O(n)。
• 大O表示法只关注最高阶项，忽略常数系数和低阶项，所以2n的量级就是O(n)，不需要保留系数2。

另外提个代码小问题：当前代码默认输入的n≥2，如果输入n=1，访问wektor[1]会触发数组越界错误，实际使用时需要加个n的合法性判断。

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