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