求助一个算法问题

V2EX = way to explore

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

已注册用户请登录

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

请问有没有可能在O(nlogn)时间里同时完成排序和累积求和？
例如：
输入 {5, 2, 1, 3, 4}, 排序后是{1, 2, 3, 4, 5}, 再累积求和后是{1, 3, 6, 10, 15}
输出{1, 3, 6, 10, 15}.

10 条回复 1970-01-01 08:00:00 +08:00

013231

2013-01-31 07:25:36 +08:00

O(nlogn) + O(n)是O(nlogn).

uoryon

2013-01-31 08:20:12 +08:00

可是尝试计数排序...但是对数据有些许限制

laskuma

2013-01-31 09:03:58 +08:00

@uoryon 数据量小的时候计数排序没优势啊。常数项太大了。
1楼正解

notonlysuccess

2013-01-31 10:14:58 +08:00

@laskuma
@013231 O(nlogn+n)不就是O(nlogn)....么

laskuma

2013-01-31 10:33:07 +08:00

@notonlysuccess 1楼意思是O(nlogn) + O(n)(依然)还是O(nlogn)

test123

2013-02-01 03:02:26 +08:00

多谢回复，数量级上去了之后nlogn跟nlogn+n差距也不小呀。

txx

2013-02-01 05:04:28 +08:00

@test123 不会的...

这么看基本上可以忽略不计了

66450146

2013-02-01 09:45:38 +08:00

@test123 数量级越大 nlogn 和 nlogn + n 差距越小的吧。。。。

ivanlw

2013-02-21 13:00:12 +08:00

@txx 这个什么软件，好棒……能推荐下么？

laskuma

2013-02-21 13:01:46 +08:00

@ivanlw OSX原生grapher