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

问一道简单的线性非齐次递推式的解法

  •  1
     
  •   hx1997 · 2018-03-27 14:34:26 +08:00 via Android · 5237 次点击
    这是一个创建于 2193 天前的主题,其中的信息可能已经有所发展或是发生改变。
    T(n)=T(n/2)+T(n/4)+cn, c 为常数. T(1)=1.
    是作业题,我太蠢不会解。注意是求非递推解,不是求渐进的界。迭代法不好用,特征方程和主定理用不了。扔进 WolframAlpha 解不出来(
    也不用解出来,告诉我解法的关键词就好了…
    9 条回复    2018-03-28 01:43:37 +08:00
    ynyounuo
        1
    ynyounuo  
       2018-03-27 15:37:32 +08:00   ❤️ 1
    随手瞎算的:
    T(1) = 1

    T(2) = T(1) + T(1/2) + cn
    = 1 + T(1/2) + cn

    T(4) = T(2) + T(1) + cn
    = (1 + T(1/2) + cn) + 1 + cn
    = 1 + 1 + T(1/2) + 2 * cn

    T(8) = T(4) + T(2) + cn
    = (1 + 1 + T(1/2) + 2 * cn) + (1 + T(1/2) + cn) + cn
    = 1 + 1 + 1 + 2T(1/2) + 3 * cn

    T(n) = log_2(n) + (log_2(n) - 1) * T(1/2) + c * log_2(n) * n


    Mathematica 的结果:
    hx1997
        2
    hx1997  
    OP
       2018-03-27 17:47:58 +08:00 via Android
    @ynyounuo 完了,跟我算的完全不一样… 你的是 O(nlogn),Mathematica 的结果是 O(n^2),我的是 O(n)……
    hx1997
        3
    hx1997  
    OP
       2018-03-27 17:49:23 +08:00 via Android
    @ynyounuo 怀疑题目出错了,哪里会这么难…
    hx1997
        4
    hx1997  
    OP
       2018-03-27 17:52:12 +08:00 via Android
    @hx1997 咦好像又不是 O(n^2),当我没说
    ynyounuo
        5
    ynyounuo  
       2018-03-27 19:50:57 +08:00 via iPhone
    @hx1997
    一楼明显有问题,可以忽略。
    Mathematica 算带对数的运算就很鸡肋,也没啥参考性。
    如果我想的没错的话,这题应该无解,除非给出另外一个 T(c) = d。
    hx1997
        6
    hx1997  
    OP
       2018-03-27 21:50:49 +08:00 via Android
    @ynyounuo 嗯,我觉得应该是让我们给出个界比较合理,谢谢啦
    Xs0ul
        7
    Xs0ul  
       2018-03-27 22:25:03 +08:00   ❤️ 2
    @hx1997 #6 试试变量代换,s = log_2(n), n = 2 ^ s

    递推式等价的应该变成 T(2^s) = T(2^(s-1)) + T(2^(s-2)) + c * 2 ^ s

    定义 R(s) = T(2^s), 改写为 R(s) = R(s-1) + R(s-2) + c * 2 ^ s

    齐次部分是斐波那契数列, 最后的 c * 2 ^ s,凑了下是 G(s) = c * 2 ^ (s+2)

    所以 R(s) = F(s) + G(s),其中 F 是斐波那契的解

    最后得到 T(n) = R(log_2(n)) = F(log_2(n)) + G(log_2(n))

    以上完全是按照函数来做的,因为原来定义里有 1/2,已经不算是数列了
    hx1997
        8
    hx1997  
    OP
       2018-03-28 01:36:26 +08:00 via Android
    @Xs0ul 真的解出来了,谢谢大佬!🙏
    hx1997
        9
    hx1997  
    OP
       2018-03-28 01:43:37 +08:00 via Android
    @Xs0ul 看了这方法,只能感叹一句太精妙了… 之前用递归树算的 O(n),也没办法给出具体表达式。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3257 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:03 · PVG 20:03 · LAX 05:03 · JFK 08:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.