澄清排序网络大小的上限和下限
Clarification on sorting-networks-size upper and lower bound
参考这篇维基百科的文章：https://en.wikipedia.org/wiki/Sorting_network，重点放在段落构建排序网络。
您能解释一下 Size, upper bound 和 Size, lower bound（在 table 中）是什么吗？
我希望 lower bound 指的是对 n 个数字的输入进行正确排序所需的最少连接数（我说得对吗？）。如果是这样，为什么还要使用 upper bound？从理论上讲，可以使用比 upper bound 更大的连接数，那么如何建立呢？
我也阅读了链接的论文（参考文献 11），但我仍然感到困惑。
table后面的段落提示了上限和下限的含义：
For one to ten inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉.
table 中的“上限”显然对应于给定数量的待排序元素的当前已知 最优化排序网络的大小。已知的 1 到 10 个元素的尺寸最优排序网络已经被证明是最优的，但是我们不确定已知的更多元素的尺寸最优排序网络实际上是否是最优的。 «下界»对应于排序给定数量的元素的排序网络的理论最小大小：可能不存在这种大小的排序网络，但我们尚未证明这一点。
总结一下：
- «上限»表示已找到的尺寸最优化的排序网络。
- « 下界 » 表示网络的理论最小尺寸。目前还没有证明这样的网络不存在，但我们也没有找到任何这种规模的可行网络。
作为旁注，我维护 a library with size-optimal sorting networks, and their sizes correspond to the « upper bound » from the table (see also the documentation and the implementation)。
参考这篇维基百科的文章：https://en.wikipedia.org/wiki/Sorting_network，重点放在段落构建排序网络。
您能解释一下 Size, upper bound 和 Size, lower bound（在 table 中）是什么吗？
我希望 lower bound 指的是对 n 个数字的输入进行正确排序所需的最少连接数（我说得对吗？）。如果是这样，为什么还要使用 upper bound？从理论上讲，可以使用比 upper bound 更大的连接数，那么如何建立呢？
我也阅读了链接的论文（参考文献 11），但我仍然感到困惑。
table后面的段落提示了上限和下限的含义：
For one to ten inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉.
table 中的“上限”显然对应于给定数量的待排序元素的当前已知 最优化排序网络的大小。已知的 1 到 10 个元素的尺寸最优排序网络已经被证明是最优的，但是我们不确定已知的更多元素的尺寸最优排序网络实际上是否是最优的。 «下界»对应于排序给定数量的元素的排序网络的理论最小大小：可能不存在这种大小的排序网络，但我们尚未证明这一点。
总结一下：
- «上限»表示已找到的尺寸最优化的排序网络。
- « 下界 » 表示网络的理论最小尺寸。目前还没有证明这样的网络不存在，但我们也没有找到任何这种规模的可行网络。
作为旁注，我维护 a library with size-optimal sorting networks, and their sizes correspond to the « upper bound » from the table (see also the documentation and the implementation)。