请教一个简单的算法问题

[levelworm]

前情提要：快四十多了心血来潮回学校修计算机。。。说这个目的是证明我现在智商不足了。

题目如下：

**Rank with lg N two-way compares. **

Implement rank() so that it uses ~ 1 lg N two-way compares (instead of ~ 1 lg N 3-way compares).

我这里没明白的是，怎么可能做得到 lgN 次对比？他这个 lgN 就是 2 为底的对数。比如说一个数组 1, 3, 2, 4，两次对比怎么也不够算 rank 的吧？我是哪里忽略了么？

[zhongrs232]

只有排序好才有可能 lgN 吧，不排序的话绝对不可能 lgN 求 rank()， 是不是题目少条件了

[lidlesseye11]

完蛋，连题目都看不懂了。。

[GuuJiang]

不清楚题目里说的 rank 是哪一种定义，假如表示的是在有序序列中的索引，那么结论是不可能的

[GuuJiang]

@GuuJiang 不小心发出来了，接上文
用反证法，假设真的存在 O(lgN)的基于比较的计算 rank 的算法，那么只需要运行一遍这个算法，同时按照计算得到的 rank 把元素放到目标数组的相应位置，于是你就得到了一个基于比较的 O(lgN)的排序算法，然而众所周知，基于比较的排序算法复杂度下界为 O(NlgN)

[ipwx]

@GuuJiang 你这不成立啊。 你看，如果我要求解的是某个数在这列数中的 rank 呢？ N 个数求出 rank， 每个数 log N，合起来就是 N log N 不是？

[dangyuluo]

@GuuJiang 反证法的要义是用某个假设推导出和该假设矛盾的推论，你这个不是反证法。抱歉挖坟了。