1679
правок
Изменения
м
Первый, наивный способ - перебрать все перестановки из n элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует <tex> O(n! \cdot Comp(n)) </tex> действий, где <tex> Comp(n) </tex> - количество компараторов в сети из n элементов. Обычно это количество можно оценить как <tex> n^2 \log n </tex>(сеть Бэтчера), то есть получаем асимптотику <tex> O(n! n^2 \log n) </tex>, то есть при n, равном уже 10, проверить сеть очень проблематично.__TOC__
Нет описания правки
Есть два способа проверить сеть из n компараторов на то, что она сортирующая.
== Первый способ ==
Первый, наивный способ - перебрать все перестановки из n элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует <tex> O(n! \cdot Comp(n)) </tex> действий, где <tex> Comp(n) </tex> - количество компараторов в сети из n элементов. Обычно это количество можно оценить как <tex> n \log^2 n </tex>(сеть Бэтчера), то есть получаем асимптотику <tex> O(n! n \log^2 n) </tex>, то есть при n, равном уже 10, проверить сеть очень проблематично.
== Второй способ ==
Второй способ основывается на предположении что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Если мы докажем это, то сможем проверять сеть за <tex> O(2^n \cdot Comp(n)) </tex>, что намного быстрее.
=== Доказательство 0-1 принципа ===
{{ Определение
| definition =
</tex> . Очевидно, она монотонная. Заметим, что <tex> f(b_i) = 1 </tex>, а <tex> f(b_{i + 1}) = 0 </tex>, то есть <tex> f(b) </tex>, или <tex> f(N(a)) </tex> - не отсортирована. Так как <tex> f </tex> и <tex> N </tex> коммутируют, <tex> N(f(a)) </tex> - также не отсортирована. Но по предположению теоремы, все последовательности из нулей и единиц сеть сортировать умеет, то есть такой последовательности <tex> a </tex> не найдется, то есть сеть компараторов является сортирующей.
}}
== Источники ==
* [http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.html Sorting networks]
* [http://en.wikipedia.org/wiki/Sorting_network Wikipedia - Sorting networks]
* Дональд Кнут - Искусство программирования. Том 3. Глава 5.3.4, стр. 249
