V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
levelworm
V2EX  ›  算法

请教一个简单的算法问题

  •  
  •   levelworm · 2021-03-27 10:04:23 +08:00 · 1535 次点击
    这是一个创建于 1097 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    题目如下:

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

    6 条回复    2021-05-13 14:12:22 +08:00
    zhongrs232
        1
    zhongrs232  
       2021-03-27 13:19:23 +08:00
    只有排序好才有可能 lgN 吧,不排序的话绝对不可能 lgN 求 rank(), 是不是题目少条件了
    lidlesseye11
        2
    lidlesseye11  
       2021-03-27 14:53:36 +08:00
    完蛋,连题目都看不懂了。。
    GuuJiang
        3
    GuuJiang  
       2021-03-27 17:53:09 +08:00
    不清楚题目里说的 rank 是哪一种定义,假如表示的是在有序序列中的索引,那么结论是不可能的
    GuuJiang
        4
    GuuJiang  
       2021-03-27 17:56:18 +08:00
    @GuuJiang 不小心发出来了,接上文
    用反证法,假设真的存在 O(lgN)的基于比较的计算 rank 的算法,那么只需要运行一遍这个算法,同时按照计算得到的 rank 把元素放到目标数组的相应位置,于是你就得到了一个基于比较的 O(lgN)的排序算法,然而众所周知,基于比较的排序算法复杂度下界为 O(NlgN)
    ipwx
        5
    ipwx  
       2021-03-27 18:44:06 +08:00
    @GuuJiang 你这不成立啊。 你看,如果我要求解的是某个数在这列数中的 rank 呢? N 个数求出 rank, 每个数 log N,合起来就是 N log N 不是?
    dangyuluo
        6
    dangyuluo  
       2021-05-13 14:12:22 +08:00
    @GuuJiang 反证法的要义是用某个假设推导出和该假设矛盾的推论,你这个不是反证法。抱歉挖坟了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3075 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:50 · PVG 20:50 · LAX 05:50 · JFK 08:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.