66
правок
Изменения
Нет описания правки
Пусть $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 Rightarrow c \cdot n \log n \leqslant \dfrac{n}{2}\cdot d \rightarrow Rightarrow 2c\log n \leqslant d \rightarrow Rightarrow d = \Omega{(\log n})$
}}
