66
правок
Изменения
Нет описания правки
|statement=Не существует структуры данных, которая одновременно поддерживает добавление элементов и извлечение минимума за амортизированное время <tex> O(1) </tex>.
|proof=Если бы такая структура существовала, то с её помощью можно было бы отсортировать все элементы за амортизированное время <tex>O(n)</tex> {{---}} добавить все элементы, а затем извлечь минимальный <tex>n</tex> раз. Можно заметить, что теореме даётся оценка на истинную нижнюю границу, а в данном утверждении фигурирует амортизированное время. Но этот факт не является проблемой, так как амортизированное время <tex> O(1) </tex> на одну операцию в случае <tex> n </tex> операций даст суммарное истинное время <tex> O(n) </tex>.
}}
{{Утверждение
|statement=Любая сортирующая сеть с $n$ нитями имеет размер $\Omega(n \log n)$.
|proof=Каждый компаратор реализует одно сравнение двух элементов.
Поэтому сортирующая сеть является алгоритмом сортировки, который основан на сравнениях, при чем количества компараторов и сравнений в этом алгоритме совпадают. Значит, их $\Omega(n \log n)$
}}
{{Утверждение
|statement=Любая сортирующая сеть с $n$ нитями имеет глубину $\Omega(\log n)$.
|proof=Каждый компаратор реализует одно сравнение двух элементов.Поэтому сортирующая сеть является алгоритмом сортировки, который основан на сравнениях.
На каждом слое может быть не более $\dfrac{n}{2}$ компараторов, так как внутри одного слоя гнезда компаратора крепятся к разным нитям, а их $n$.
