未分類
16 3 月 2021

请教一个简单的算法问题

请教一个简单的算法问题

資深大佬 : levelworm 0

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

题目如下：

**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 的吧？我是哪里忽略了么？

大佬有話說 (5)

  • 資深大佬 : 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 不是？