Какова временная сложность этого конкретного кода?

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).

Добавление: Поскольку вы используете целые числа в качестве ключей и не используете пользовательскую хэш-функцию, я думаю, что можно с уверенностью предположить, что O (1) для find, так как вы, вероятно, не доберетесь до худшего случая.