59
правок
Изменения
Нет описания правки
Пусть <tex> S(n) </tex> - количество слоев в сети сортировки с <tex> n </tex> входами.
При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex>-й, добавляем <tex> n </tex> компаратор. Заметим, что с <tex> n - 2 </tex> компараторами можно сделать слои, используя слои из предыдущей сортирующей сети. Тогда остается два компаратора, которые сами являются слоями. Тем самым получили рекуррентное соотношение:
<tex> S(n + 1) = S(n) + 2 </tex> с начальными данными (<tex>S(2) = 1</tex>). Решением данного рекуррентного соотношения является <tex> S(n) = 2n - 3 </tex>. Что и требовалось доказать
