V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
This topic created in 1865 days ago, the information mentioned may be changed or developed.
前情提要：快四十多了心血来潮回学校修计算机。。。说这个目的是证明我现在智商不足了。
题目如下：
**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 Mar 27, 2021
只有排序好才有可能 lgN 吧，不排序的话绝对不可能 lgN 求 rank()， 是不是题目少条件了
|
 |
2
lidlesseye11 Mar 27, 2021
完蛋，连题目都看不懂了。。
|
 |
3
GuuJiang Mar 27, 2021
不清楚题目里说的 rank 是哪一种定义，假如表示的是在有序序列中的索引，那么结论是不可能的
|
|
4
GuuJiang Mar 27, 2021
@GuuJiang 不小心发出来了，接上文
用反证法，假设真的存在 O(lgN)的基于比较的计算 rank 的算法，那么只需要运行一遍这个算法，同时按照计算得到的 rank 把元素放到目标数组的相应位置，于是你就得到了一个基于比较的 O(lgN)的排序算法，然而众所周知，基于比较的排序算法复杂度下界为 O(NlgN) |
Select Language