Complexity of element containers

С тех порКонтейнеры<std::set>и<icl::map>являются только расширениями stl::set и stl::map, соответственно их характеристики сложности. Таким образом, их основные операции вставки (дополнения), удаления и поиска используют логарифмическое время.

Complexity of interval containers

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

Более подробная информация охарактеристиках сложностифункций iclсодержится в разделеФункциональная ссылка

Time Complexity of Addition

Следующая таблица дает временные сложности для перегруженных<operator+=>на интервальных контейнерах. Примеры<T>приведены в виде заголовков столбцов. Параметры типа<P>обозначаются во второй колонке. Третья колонка содержит конкретное заявление о сложности. Если столбец третий пуст, то в соответствующем ряду дается наихудший случайсложности.

Добавлениеэлементаилипара значений элементавсегда производится влогарифмического времени, гдеnявляется числом интервалов в интервальном контейнере. Та же самая строка сложностей относится к вставке сегмента(интервал или пара значений интервала) влучшем случае, где вставленный сегмент перекрывается только снебольшимчислом интервалов в контейнере.

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

После выполнения добавления наихудшего случая для<interval_set>или<separate_interval_sets>добавления интервала, который перекрываетnинтервалов, нам нужноnнеперекрывающихся добавленийлогарифмического времени, прежде чем мы сможем запустить другоеO(n)наихудшего добавления случая. Таким образом, у нас есть толькологарифмическое амортизированное времядля добавления интервала или пары значений интервала.

Для добавленияинтервальных контейнеровсложность составляетO(m log(n+m)]. Так длянаихудшего случая, где размеры контейнераnимравны и оба контейнера охватывают одинаковые диапазоны, сложность добавления контейнера составляетлоглайнар. В других случаях, которые часто происходят в реальных приложениях, производительность может быть намного лучше. Если добавленный контейнер<operand>намного меньше<object>и интервалы в<operand>относительно малы, производительность может быть.логарифмический. Еслиммал по сравнению сnи интервалы в<operand>велики, производительность имеет тенденцию бытьлинейной.