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