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