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

像这样的算法,它的复杂度应该怎么分析?

  •  
  •   rogerer · 2018-12-14 15:38:37 +08:00 · 2194 次点击
    这是一个创建于 1931 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这个算法是扩展约瑟夫算法。

    算法的描述: Jo

    具体的实现是这样的:

    def J(n,x):
        Dk = 1
        while Dk <= (x-1)*n: 
            Dk = math.ceil((x/(x-1))*Dk)
        return (x*n+1-Dk)
    

    我大致的想法就是解关于 k 的方程:

    eq

    从而得到 k 关于 n 和 x 的表达式,再保留高阶项得到最终的结果

    最终通过化简得到的复杂度的结果是:

    result

    但是从来没有见到过这样的复杂度...

    因为自己也刚刚开始学数据结构与算法,所以恳请各位帮忙算一算

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1266 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:52 · PVG 01:52 · LAX 10:52 · JFK 13:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.