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

求助一个算法问题

  •  
  •   test123 · 2013-01-31 07:06:18 +08:00 · 5469 次点击
    这是一个创建于 4075 天前的主题,其中的信息可能已经有所发展或是发生改变。
    请问有没有可能在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
        1
    013231  
       2013-01-31 07:25:36 +08:00   ❤️ 1
    O(nlogn) + O(n)還是O(nlogn).
    uoryon
        2
    uoryon  
       2013-01-31 08:20:12 +08:00   ❤️ 1
    可是尝试计数排序...但是对数据有些许限制
    laskuma
        3
    laskuma  
       2013-01-31 09:03:58 +08:00   ❤️ 1
    @uoryon 数据量小的时候计数排序没优势啊。 常数项太大了。
    1楼正解
    notonlysuccess
        4
    notonlysuccess  
       2013-01-31 10:14:58 +08:00   ❤️ 1
    @laskuma
    @013231 O(nlogn+n)不就是O(nlogn)....么
    laskuma
        5
    laskuma  
       2013-01-31 10:33:07 +08:00   ❤️ 1
    @notonlysuccess 1楼意思是O(nlogn) + O(n)(依然)还是O(nlogn)
    test123
        6
    test123  
    OP
       2013-02-01 03:02:26 +08:00
    多谢回复,数量级上去了之后nlogn跟nlogn+n差距也不小呀。
    txx
        7
    txx  
       2013-02-01 05:04:28 +08:00
    @test123 不会的...



    这么看 基本上可以忽略不计了
    66450146
        8
    66450146  
       2013-02-01 09:45:38 +08:00
    @test123 数量级越大 nlogn 和 nlogn + n 差距越小的吧。。。。
    ivanlw
        9
    ivanlw  
       2013-02-21 13:00:12 +08:00
    @txx 这个什么软件,好棒……能推荐下么?
    laskuma
        10
    laskuma  
       2013-02-21 13:01:46 +08:00
    @ivanlw OSX原生grapher
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2450 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 15:52 · PVG 23:52 · LAX 08:52 · JFK 11:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.