Изменения

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