635
правок
Изменения
→Следствия
{{Утверждение
|statement=Не существует структуры данных, которая поддерживает добавление элементов и извлечение минимума за амортизированное время <tex> O(1) </tex>. Даже если остальные операции могут выполняться сколько угодно долго.
|proof=Верхние границы Пусть имеется структура данных, которая поддерживает добавление элемента за время <tex> O(1) </tex>. При этом значение минимального элемента может измениться, что потребует сортировки элементов для его извлечения. Согласно теореме минимальное время для этого составляет <tex> \Omega (n \log n) </tex> времени работы пирамидальной сортировки и сортировки слиянием совпадают с нижней границей .Обратно, если имеется структура данных, которая поддерживает извлечение минимального элемента за время <tex> O(1) </tex>, требуется по крайней мере <tex>\OmegaO(n \log n)</tex> времени для наихудшего случая из теоремы о нижней границе для сортировки сравнениямикаждой операции добавления элемента с целью поддержания элементов структуры в отсортированном виде.
}}
