此特定代码的时间复杂度是多少？

Question

我创建了一个简单的程序，该程序使用无序映射来保留数组中元素的数量。我想知道以下程序的时间复杂度。只是O（n）时间吗？在无序地图上完成的操作需要多少时间？（即，在地图中查找键，如果存在，则将其值加1，如果未将其初始化，则将其加1）这是在固定时间还是对数或线性时间内完成的？如果时间不固定，那么请向我建议一种更好的方法。

#include <unordered_map>
#include<iostream>
int main()
{
        int n;
        std::cin >> n;
        int arr[100];
        for(int i=0;i<n;i++)
            std::cin >> arr[i];
        std::unordered_map<int, int> dp;
        for(int i=0; i<n; i++)
        {
            if (dp.find(arr[i]) != dp.end())
                dp[arr[i]] ++;
            else
                dp[arr[i]] = 1;
        }
}

Answer 1

文档说，std::unordered_map::find()的复杂度为

平均，最坏的情况下，容器的大小是线性的。

所以您的平均复杂度为O（n），最坏情况的复杂度为O（n ^ 2）。