V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
regicide
V2EX  ›  问与答

有一个计算时间复杂度的算法问题需要请教一下 V 友们

  •  
  •   regicide · 2017-12-12 17:01:50 +08:00 · 887 次点击
    这是一个创建于 2538 天前的主题,其中的信息可能已经有所发展或是发生改变。

    for(int i = 1; i <= n; i++)
        for (int j = 1; j <= log5(i); j += 3)
    这样的循环(主要是第二个循环)的时间复杂度应该怎样推导呢?

    5 条回复    2017-12-12 17:33:56 +08:00
    tjbwyk
        1
    tjbwyk  
       2017-12-12 17:23:21 +08:00 via Android
    大致如此? O((log5(n!)/3))=O(log5(n!))<=O(log5(n^n))=O(n log5(n))=O(n log(n))
    tjbwyk
        2
    tjbwyk  
       2017-12-12 17:25:43 +08:00 via Android
    或者假设第二层循环上限是 log5(n),那原来的时间复杂度<=O(n*log5(n)/3),化简是一样的
    tjbwyk
        3
    tjbwyk  
       2017-12-12 17:27:41 +08:00 via Android
    已经忘了怎么算了。。比如时间复杂度的下限什么的。。
    regicide
        4
    regicide  
    OP
       2017-12-12 17:30:21 +08:00
    @tjbwyk 就是有点纠结 log5(n)这个点 感谢 看来我还得回去仔细看看书
    tjbwyk
        5
    tjbwyk  
       2017-12-12 17:33:56 +08:00 via Android
    @regicide 是 log5->log 么?换底之后可以提一个常数项出来
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2769 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 08:30 · PVG 16:30 · LAX 00:30 · JFK 03:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.