Разъяснение по верхним и нижним границам размера сортировочных сетей

Question

Ссылаясь на эту статью в Википедии: https://en.wikipedia.org/wiki/Sorting_network, с акцентом на параграфе " Создание сетей сортировки".

Можете ли вы объяснить, что Size, upper bound а также Size, lower bound (в таблице) есть? Я ожидаю, что lower bound относится к минимальному количеству соединений, необходимых для правильной сортировки ввода из n чисел (я прав?). Если так, то зачем upper bound? Теоретически, можно использовать несколько соединений, превышающих upper bound так как это можно установить? Я также прочитал связанную статью (ссылка 11), но я все еще в замешательстве.

Answer 1

Абзацы после таблицы дают подсказку о значении верхней и нижней границ:

Для одного-десяти входов известны минимальные (т. Е. Оптимальные по размеру) сортировочные сети, а для более высоких значений нижние границы их размеров S(n) могут быть получены индуктивно с использованием леммы Ван Вурхиса: S (n + 1) ≥ S(n) + ⌈log2 (n) ⌉.

"Верхняя граница" в таблице, очевидно, соответствует размеру наиболее оптимальной по размеру сети сортировки, известной в настоящее время для данного количества элементов для сортировки. Доказано, что известные сети сортировки с оптимальным размером для 1-10 элементов являются оптимальными, но мы не уверены, что известные сети сортировки с оптимальным размером для большего количества элементов на самом деле являются наиболее оптимальными. "Нижняя граница" соответствует теоретическому минимальному размеру сортировочной сети для сортировки заданного количества элементов: возможно, что сортировочная сеть такого размера не существует, но мы еще не доказали это.

Подводить итоги:

• "Верхняя граница" представляет наиболее оптимальную по размеру сортировочную сеть из найденных.
• "Нижняя граница" представляет теоретический минимальный размер сети. Доказано, что такой сети не существует, но мы не нашли ни одной жизнеспособной сети такого размера.

---

В качестве дополнительного примечания я веду библиотеку с оптимальными по размеру сетями сортировки, а их размеры соответствуют "верхней границе" из таблицы (см. Также документацию и реализацию).