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