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

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

  •  1
     
  •   hx1997 · 330 天前用 Android 发布 · 2001 次点击
    这是一个创建于 330 天前的主题,其中的信息可能已经有所发展或是发生改变。
    T(n)=T(n/2)+T(n/4)+cn, c 为常数. T(1)=1.
    是作业题,我太蠢不会解。注意是求非递推解,不是求渐进的界。迭代法不好用,特征方程和主定理用不了。扔进 WolframAlpha 解不出来(
    也不用解出来,告诉我解法的关键词就好了…
    9 回复  |  直到 2018-03-28 01:43:37 +08:00
        1
    ynyounuo   330 天前   ♥ 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 的结果:
        2
    hx1997   330 天前 via Android
    @ynyounuo 完了,跟我算的完全不一样… 你的是 O(nlogn),Mathematica 的结果是 O(n^2),我的是 O(n)……
        3
    hx1997   330 天前 via Android
    @ynyounuo 怀疑题目出错了,哪里会这么难…
        4
    hx1997   330 天前 via Android
    @hx1997 咦好像又不是 O(n^2),当我没说
        5
    ynyounuo   330 天前 via iPhone
    @hx1997
    一楼明显有问题,可以忽略。
    Mathematica 算带对数的运算就很鸡肋,也没啥参考性。
    如果我想的没错的话,这题应该无解,除非给出另外一个 T(c) = d。
        6
    hx1997   330 天前 via Android
    @ynyounuo 嗯,我觉得应该是让我们给出个界比较合理,谢谢啦
        7
    Xs0ul   330 天前   ♥ 1
    @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,已经不算是数列了
        8
    hx1997   330 天前 via Android
    @Xs0ul 真的解出来了,谢谢大佬!🙏
        9
    hx1997   330 天前 via Android
    @Xs0ul 看了这方法,只能感叹一句太精妙了… 之前用递归树算的 O(n),也没办法给出具体表达式。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3974 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 17ms · UTC 06:00 · PVG 14:00 · LAX 22:00 · JFK 01:00
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1