Сложность вставки N элементов в пустой std :: map
Я хотел бы знать сложность следующей функции.
Я знаю, что std :: map реализован как красно-черное дерево, и сложность вставки равна O (logN).
Но как рассчитать, если я продолжу добавлять N элементов на пустую карту?
void add(int N, std::map<int, int>& map) {
for (int i = 0; i < N; ++i) {
map[i] = i;
}
}
Заранее спасибо,
Решение
Вы делаете O (log N) N раз, так что это O (N log N).
Другие решения
Дерево R-B является сбалансированным двоичным деревом. Операции вставки в основном находят позицию вставки, выделяют пространство для вновь вставленного узла и корректируют указатели, а затем перебалансируют дерево R-B. Сложность вставки O (logN).
Поскольку в вашем случае вы сначала решаете сложность определенной операции, то есть вставки со сложностью log (N), а затем выясняете, сколько раз эта операция используется. Вот почему у нас есть N (logN).
O (logN) означает, что порядок роста времени по отношению к количеству элементов в контейнере не превышает порядка logN. Это на самом деле не означает, что фактическое время используется logN.
Если ваша заявка является критикой времени, вы можете рассмотреть возможность использования unordered_map так как сложность времени вставки постоянна. Вы отображаете от int до int, поэтому в этом случае должно быть прекрасно использовать unordered_map.
Кстати: в вашей формуле log0 не определен, когда нет элементов для вставки, вы не выполняете операцию вставки.
Вы задаете разумный вопрос.
Вставляя N элементов в дерево, которое начиналось пустым, вы начинаете с log (0) и переходите к log (N). Это означает, что ваше общее среднее действительно log(N/2) вместо log(N),
Однако в случае логарифма это не имеет большого значения — общая сложность все еще логарифмическая. То, что вы сделали, фактически изменило база логарифма.
detector