algorithm - 如何证明排序网络深度的下界是lgn？

Question

我正在尝试回答 clrs intro to alg edition2 练习。在第 27.1-4 章中有一个练习说:“证明 n 个输入的任何排序网络的深度至少为 lg n”。所以我认为我们最多可以在每个深度使用 (n/2) 个比较器，如果我们假设我们已经找到了一个比较器的组合，可以对深度 1 中的 (n/2) 个数字进行排序，那么我们需要对另一个进行排序(n/2) 个数字。因此，如果我们继续做同样的事情，我们会在每个深度将 n 除以 2，因此排序网络的深度将为 lgn。这个结论错了吗？如果这是证明排序网络深度下限的正确方法。

Answer 1

我能想到两个。

首先，您可以将 n 个元素的排序网络视为基于比较的排序算法，后者的下界意味着该网络执行 lg n! = n lg n − n + O(log n) 次比较，除以每个级别的 n/2 次比较是 2 lg n − 1 + O((log n)/n) ≥ lg n 如果 n ≥ 2(你可以验证n = 1 手动)。

另一个是在 r 轮之后，每个输入最多可以被洗牌到 2^r 个不同的位置。这可以通过归纳来证明。每个输入必须能够到达每个输出，所以 2^r ≥ n，这意味着 r ≥ lg n。

(这种问题以后最好在cs.stackexchange.com上问。)