如何证明排序网络深度的下界是lgn？
How to prove that lower bound of a sorting networks depth is lgn?
我正在尝试回答 clrs intro to alg edition2 练习。在第 27.1-4 章中有一个练习说：“证明 n 个输入的任何排序网络的深度至少为 lg n”。
所以我认为我们最多可以在每个深度使用 (n/2) 个比较器，如果我们假设我们已经找到了可以对 depth1 中的数字进行排序 (n/2) 的比较器组合，那么我们需要对数字的另一个 (n/2) 进行排序。因此，如果我们继续做同样的事情，我们会在每个深度将 n 除以 2，因此排序网络的深度将为 lgn。
这个结论错了吗？如果这是证明排序网络深度下限的正确方法。
我能想到两个。
首先，您可以将 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轮之后，每个输入最多可以被洗牌到2r个不同的位置。这可以通过归纳来证明。每个输入必须能够到达每个输出，所以 2r ≥ n，这意味着 r ≥ lg n.
（这种问题以后最好在cs.stackexchange.com上问。）
我正在尝试回答 clrs intro to alg edition2 练习。在第 27.1-4 章中有一个练习说：“证明 n 个输入的任何排序网络的深度至少为 lg n”。 所以我认为我们最多可以在每个深度使用 (n/2) 个比较器，如果我们假设我们已经找到了可以对 depth1 中的数字进行排序 (n/2) 的比较器组合，那么我们需要对数字的另一个 (n/2) 进行排序。因此，如果我们继续做同样的事情，我们会在每个深度将 n 除以 2，因此排序网络的深度将为 lgn。 这个结论错了吗？如果这是证明排序网络深度下限的正确方法。
我能想到两个。
首先，您可以将 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轮之后，每个输入最多可以被洗牌到2r个不同的位置。这可以通过归纳来证明。每个输入必须能够到达每个输出，所以 2r ≥ n，这意味着 r ≥ lg n.
（这种问题以后最好在cs.stackexchange.com上问。）