В чем сложность map/set::insert, если вы предоставили правильный намек на итератор?

Это O(1) или O(logN), но с меньшим коэффициентом?

Если это не указано, я бы, по крайней мере, хотел бы знать ответ, основанный на разумном предположении, что карта/набор реализованы с использованием красно-черного дерева или дерева AVL. Общий алгоритм вставки элемента, я думаю, выглядит примерно так:

  • найти нужное место - O(logN)
  • сделать фактическую вставку - ?
  • перебалансировать дерево при необходимости - ?

Теперь, если мы предоставим правильную подсказку итератора, то первый шаг станет O(1). Другие шаги также O(1) или O(logN)?


c++ set data-structures binary-search-tree tree-balancing
person Armen Tsirunyan    schedule 11.12.2014    source источник
comment
Подумай об этом. Какие шаги вы бы сделали, если бы писали метод вставки? Какие шаги вы бы предприняли, если бы вам нужно было сбалансировать дерево? Зависят ли шаги от количества узлов?   -  person George Houpis    schedule 11.12.2014
comment
Вот несколько ответов, которые могут быть полезны: stl-map-performance, why-is-stdmap-implemented-as-red-black-tree, difference-between-red-black-trees-and-avl-trees   -  person nouney    schedule 11.12.2014

Ответы (3)


arrow_upward
5
arrow_downward

Стандарт не говорит, как должны быть реализованы контейнеры, поэтому вы не можете рассчитывать на дерево RB или AVL. На практике... ограничения сложности таковы, что я не знаю других реализаций, которые соответствовали бы всем требованиям. Но именно в ограничениях сложности вы найдете ответ: в общем случае логарифмическая, но амортизированная постоянная, если t вставляется прямо перед p. Таким образом, если подсказка верна, реализация должна быть такой, чтобы вставка выполнялась за O(1).

person James Kanze    schedule 11.12.2014
comment
Вот как эта проблема эволюционировала от C++03 до C++11: open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html - person Howard Hinnant; 11.12.2014

arrow_upward
2
arrow_downward

  • найти нужное место - O(logN)
  • выполнить фактическую вставку - O(1), независимо от того, является ли это деревом AVL или RB
  • при необходимости перебалансируйте дерево - я не знаю точной нотации BIG-O для дерева AVL, но для дерева RB это O(1).

Подсказка итератора не затрагивает шаг 2 (вставка) и шаг 3 (перебалансировка). Предоставляя итератор, вы просто выполняете шаг № 1 («находите нужное место») самостоятельно, общая сложность такая же.

person nouney    schedule 11.12.2014
comment
сложность этой операции для дерева RB составляет O (1). -- ? - person n. 1.8e9-where's-my-share m.; 11.12.2014
comment
Откуда вы берете эту сложность? - person n. 1.8e9-where's-my-share m.; 11.12.2014
comment
@н.м. Я получил его от здесь. - person nouney; 11.12.2014
comment
Из вашей ссылки: (хотя, возможно, придется изучить узлы O (log n), чтобы решить, где необходимы вращения). - person n. 1.8e9-where's-my-share m.; 11.12.2014
comment
@н.м. Не стесняйтесь отвечать - person nouney; 11.12.2014
comment
Не беспокойтесь, амортизированная сложность в любом случае равна O(1). - person n. 1.8e9-where's-my-share m.; 12.12.2014

arrow_upward
0
arrow_downward

Первый стандарт никогда не говорил точно, какую структуру данных он использует для реализации множества. Просто сложность операций над ними помогает нам ориентироваться на некое самобалансирующееся бинарное дерево поиска.

Да, если вы предоставите правильную подсказку для вставки, поместив правильный итератор, тогда все шаги будут амортизированы O (1) как шаги 2 и 3 и не будут зависеть ни от чего.

person ravi    schedule 11.12.2014