这是一个创建于 1345 天前的主题，其中的信息可能已经有所发展或是发生改变。
前情提要：快四十多了心血来潮回学校修计算机。。。说这个目的是证明我现在智商不足了。
题目如下：
**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 的吧？我是哪里忽略了么？
 |
1
zhongrs232 2021-03-27 13:19:23 +08:00
只有排序好才有可能 lgN 吧，不排序的话绝对不可能 lgN 求 rank()， 是不是题目少条件了
|
 |
2
lidlesseye11 2021-03-27 14:53:36 +08:00
完蛋，连题目都看不懂了。。
|
 |
3
GuuJiang 2021-03-27 17:53:09 +08:00
不清楚题目里说的 rank 是哪一种定义，假如表示的是在有序序列中的索引，那么结论是不可能的
|
|
4
GuuJiang 2021-03-27 17:56:18 +08:00
@GuuJiang 不小心发出来了，接上文
用反证法，假设真的存在 O(lgN)的基于比较的计算 rank 的算法，那么只需要运行一遍这个算法，同时按照计算得到的 rank 把元素放到目标数组的相应位置，于是你就得到了一个基于比较的 O(lgN)的排序算法，然而众所周知，基于比较的排序算法复杂度下界为 O(NlgN) |
Select Language