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, проверить сеть очень проблематично.
Второй способ основывается на предположении что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Докажем Если мы докажем это, то сможем проверять сеть за <tex> O(2^n \cdot Comp(n)) </tex>, что намного быстрее.
{{ Определение
