Проверка сети компараторов на то, что она является сортирующей

Есть два способа проверить сеть из n компараторов на то, что она сортирующая.

Наивный способ

Первый, наивный способ — перебрать все перестановки из [math] n [/math] элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует [math] O(n! \cdot Comp(n)) [/math] действий, где [math] Comp(n) [/math] — количество компараторов в сети из [math]n[/math] элементов. Обычно это количество можно оценить как [math] n \log^2n [/math] (Сеть Бетчера). Таким образом, получаем асимптотику [math] O(n!n \log^2n) [/math], и при [math]n = 10[/math] проверить сеть очень проблематично.

0-1 принцип

Второй способ основывается на том, что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Таким образом, можно проверить сеть за [math] O(2^n \cdot Comp(n)) [/math], что намного быстрее.

Источники

• Sorting networks
• Wikipedia — Sorting networks
• Дональд Кнут — Искусство программирования — Том 3 — Глава 5.3.4 — стр. 249