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