V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
meteor2013
V2EX  ›  程序员

这两天在看数据结构,有个复杂度排序的问题,很迷惑,求指点。

  •  1
     
  •   meteor2013 · 2015-02-12 09:01:18 +08:00 · 3417 次点击
    这是一个创建于 3600 天前的主题,其中的信息可能已经有所发展或是发生改变。
    http://drp.io/nRF


    我的排序是
    J > I > H > F > E > D > C > B = G > A

    请大家指点
    12 条回复    2015-02-13 12:37:12 +08:00
    yujnln
        1
    yujnln  
       2015-02-12 09:06:41 +08:00
    G =O(loglogn)
    A =O(n)

    G > A 就不对了
    meteor2013
        2
    meteor2013  
    OP
       2015-02-12 09:15:30 +08:00
    @yujnln

    G: loglogn = O(logn) ,
    A: O(n)

    所以应该是: J > I > H > F > E > A > D > C > B = G

    对吧?
    juxingzhutou
        3
    juxingzhutou  
       2015-02-12 09:20:18 +08:00
    @meteor2013 loglogn就是log(log(n))这么会等于O(logn)呢
    donglingyongadls
        4
    donglingyongadls  
       2015-02-12 09:23:42 +08:00
    如果log(log(n))等于O(logn),那么log(n)就应该等于O(n)了。所以你的推论是错误的
    exch4nge
        5
    exch4nge  
       2015-02-12 09:23:48 +08:00
    关于E,e^n了,不应该是指数级的么?
    exch4nge
        6
    exch4nge  
       2015-02-12 09:26:45 +08:00
    说下我的想法,有可能不对。
    其中 J I H E是指数级别的
    A F 是多项式级别的
    B C D 是log级别的
    G是log log级别的
    硬要排序的话,J > I > H > E > F > A > D > C > B > G
    liuhaotian
        7
    liuhaotian  
       2015-02-12 09:59:27 +08:00   ❤️ 4
    @exch4nge 我和你意见基本一致。。
    Mutoo
        8
    Mutoo  
       2015-02-12 10:11:58 +08:00
    http://graph.tk/ 直接把函数图像画出来,比较直观。
    GtDzx
        9
    GtDzx  
       2015-02-12 10:20:01 +08:00
    J > I > H > E > F > A > B = C = D > G
    B C D都是 O(logn)
    gkiwi
        10
    gkiwi  
       2015-02-12 10:36:31 +08:00
    @exch4nge 一样
    saki
        11
    saki  
       2015-02-13 01:16:21 +08:00
    直接算极限然后比较就可以了
    Bearox
        12
    Bearox  
       2015-02-13 12:37:12 +08:00
    11楼正解。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2689 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 14:46 · PVG 22:46 · LAX 06:46 · JFK 09:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.