求助一个算法问题

[test123]

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

[013231]

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

[uoryon]

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

[laskuma]

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

[notonlysuccess]

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

[laskuma]

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

[test123]

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

[txx]

@test123 不会的...



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

[66450146]

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

[ivanlw]

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

[laskuma]

@ivanlw OSX原生grapher