重复使用n次t（）

Question

主方法效果很好地存在 $ t（n）= kt（a）+ cn $ ，但它没有处理问题 $$ t（n）= n ^ {\ frac {1} {3}} t（n ^ {\ frac {2} {3}}）+ n ^ 2 $$ 每个分区的分支数是 $ n $ 的函数。我想知道是否有解决这种问题的解决方案，我不知道如何解决这个问题，任何帮助都很感激！

Answer 1

您可以使用更拓展的更基本方法： \ begin {align} t（n）＆= n ^ 2 + n ^ {1/3} t（n ^ {2/3}）\\＆= n ^ 2 + n ^ {5/3} + n ^ {5/9} t（n ^ {4/9}）\\＆= n ^ 2 + n ^ {5/3} + n ^ {10/9} + n ^ {19/27} t（n ^ {8/27} ）\\＆=cdots \结束{对齐} 这表明<跨越类=“math-container”> $ t（n）= o（n ^ 2）$ 。的确，让我们试图通过诱导来证明 $ t（n）\ leq cn ^ 2 $ ： $$ t（n）\ leq n ^ 2 + n ^ {1/3} \ cdot cn ^ {4/3}= n ^ 2 \ left（1 + \ frac {c} {n ^ {1/3}}正确的）， $$ 任何 $ cn ^ 2 $ 的任何 $ c> $ c> 1 $ 和大的 $ n $ （取决于 $ c $ ）。

实际上，定义 $ s（n）= t（n） - n ^ 2 $ ，我们有 $$ s（n）= n ^ {5/3} + n ^ {1/3} s（n ^ {2/3}）， $$ 因此，相同的参数显示 $ s（n）= o（n ^ {5/3}）$ 等 $ t（n）= n ^ 2 + o（n ^ {5/3}）$ 。以同样的方式，我们可以获得 $ t（n）= n ^ 2 + n ^ {5/3} + o（n ^ {10/9}）$ 等等。