66
правок
Изменения
Нет описания правки
{{Утверждение
|statement=Не существует структуры данных, которая одновременно поддерживает добавление элементов и извлечение минимума за амортизированное время <tex> OЛюбая сортирующая сеть с $n$ нитями имеет размер $\Omega(1n \log n) </tex>$. |proof=Если бы такая структура существовала, то с её помощью можно было бы отсортировать все элементы за амортизированное время <tex>O(n)</tex> {{---}} добавить все элементы, а затем извлечь минимальный <tex>n</tex> разКаждый компаратор реализует одно сравнение двух элементов. Можно заметитьПоэтому сортирующая сеть является алгоритмом сортировки, что теореме даётся оценка который основан на истинную нижнюю границусравнениях, а при чем количества компараторов и сравнений в данном утверждении фигурирует амортизированное времяэтом алгоритме совпадают. Но этот факт не является проблемойЗначит, так как амортизированное время <tex> Oих $\Omega(1) </tex> на одну операцию в случае <tex> n </tex> операций даст суммарное истинное время <tex> O(\log n) </tex>.$
}}
{{Утверждение
|statement=Любая сортирующая сеть с $n$ нитями имеет глубину $\Omega(\log n)$.
|proof=
На каждом слое может быть не более $\dfrac{n}{2}$ компараторов, так как внутри одного слоя гнезда компаратора крепятся к разным нитям, а их $n$.
Пусть $d$ {{---}} количество слоев этой сети. Тогда количество компараторов $k \leqslant \dfrac{n}{2} \cdot d$
Теорема утверждает, что количество сравнений этого алгоритма (то есть количество компараторов) $k = \Omega(n\log n)$.
Это означает, что найдется такая константа $c$, что $k \geqslant c \cdot n \log n$.
Таким образом $c \cdot n \log n \leqslant k \leqslant \dfrac{n}{2} \cdot d \Rightarrow c \cdot n \log n \leqslant \dfrac{n}{2}\cdot d \Rightarrow 2c\log n \leqslant d \Rightarrow d = \Omega(\log n)$
}}
{{Утверждение
|statement=Не существует алгоритма добавления элемента в упорядоченный массив с сохранением порядка, за истинное время $\mathcal{o}(\log n)$, где $n$ {{---}} количество элементов в массиве,
|proof=Допустим, есть такой алгоритм. Тогда создадим пустой массив и будем последовательно добавлять в него элементы массива, который хотим отсортировать. В итоге на выходе алгоритма получим отсортированный массив.
Тогда сравнений будет $\mathcal{o}(\log 1 + \log 2 + \ldots + \log{(n-1)}) = \mathcal{o}(n\log n)$. Но теорема утверждает, что их должно быть $\Omega(n\log n)$.
}}
{{Утверждение
|statement=Не существует структуры данных, которая одновременно поддерживает добавление элементов и извлечение минимума за амортизированное время <tex> \mathcal{o}(\log n) </tex>.
|proof=Если бы такая структура существовала, то с её помощью можно было бы отсортировать все элементы за амортизированное время <tex>\mathcal{o}(n \log{n})</tex> {{---}} добавить все элементы,
а затем извлечь минимальный <tex>n</tex> раз. Можно заметить, что теореме даётся оценка на истинную нижнюю границу, а в данном утверждении фигурирует амортизированное время.
Но этот факт не является проблемой, так как амортизированное время <tex> \mathcal{o}(\log n) </tex> на одну операцию в случае <tex> n </tex> операций даст суммарное истинное время <tex> \mathcal{o}(n \log n) </tex>.
}}
== См. также ==
* [[Сортирующие_сети]]
* [[Быстрая_сортировка]]
* [[Двоичная_куча]]
==Источники информации==
