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

Материал из Викиконспекты
Перейти к: навигация, поиск

Есть два способа проверить сеть из 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 принцип[править]

Основная статья: 0-1 принцип

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

Источники[править]