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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3565 天前的主题，其中的信息可能已经有所发展或是发生改变。

http://drp.io/nRF

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

请大家指点

12 条回复 • 2015-02-13 12:37:12 +08:00

yujnln

2015-02-12 09:06:41 +08:00

G =O(loglogn)
A =O(n)

G > A 就不对了

meteor2013

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

2015-02-12 09:20:18 +08:00

@meteor2013 loglogn就是log(log(n))这么会等于O(logn)呢

donglingyongadls

2015-02-12 09:23:42 +08:00

如果log(log(n))等于O(logn)，那么log(n)就应该等于O(n)了。所以你的推论是错误的

exch4nge

2015-02-12 09:23:48 +08:00

关于E，e^n了，不应该是指数级的么？

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

2015-02-12 09:59:27 +08:00

@exch4nge 我和你意见基本一致。。

Mutoo

2015-02-12 10:11:58 +08:00

http://graph.tk/ 直接把函数图像画出来，比较直观。

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

2015-02-12 10:36:31 +08:00

saki

2015-02-13 01:16:21 +08:00

直接算极限然后比较就可以了

Bearox

2015-02-13 12:37:12 +08:00

11楼正解。