1679
правок
Изменения
м
Новая страница: «Есть два способа проверить сеть из n компараторов на то, что она сортирующая. Первый, наивн…»
Есть два способа проверить сеть из n компараторов на то, что она сортирующая.
Первый, наивный способ - перебрать все перестановки из 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, проверить сеть очень проблематично.
Второй способ основывается на предположении что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Докажем это.
Первый, наивный способ - перебрать все перестановки из 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, проверить сеть очень проблематично.
Второй способ основывается на предположении что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Докажем это.
