Проверка сети компараторов на то, что она является сортирующей
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Есть два способа проверить сеть из n компараторов на то, что она сортирующая.
Содержание
Наивный способ
Первый, наивный способ — перебрать все перестановки из Сеть Бетчера). Таким образом, получаем асимптотику , и при проверить сеть очень проблематично.
элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует действий, где — количество компараторов в сети из элементов. Обычно это количество можно оценить как (0-1 принцип
Второй способ основывается на том, что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Таким образом, можно проверить сеть за
, что намного быстрее.Источники
- Sorting networks
- Wikipedia — Sorting networks
- Дональд Кнут — Искусство программирования — Том 3 — Глава 5.3.4 — стр. 249