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> времени для каждой операции добавления элемента с целью поддержания элементов структуры в отсортированном видераз.
}}
