如何用两个单独的收敛速度解决递归

Question

解决以下递归的正确方法是什么： $ t（n）= t（\ lceil \ frac {n} {2} \ rceil）+ t（n-2）$

或基本上有两个部分的递归，它们以不同的速率收敛。

我正在尝试得到大 $ o $ 近似，尽可能紧，但我无法用任何“传统”方法弄清楚。

Answer 1

如果您使用初始条件 $ t（0）= 0 $ 和 $ t（1）= 1 $ 然后你得到 a018819 （最多转移），这基本上是 a000123 。已知渐近学称为 $ t（n）= n ^ {\ theta（\ log n）} $ 。第二个条目下的参考文献包含更准确的渐近信息。

更明确地，A018819满足重复性 $ a（2m + 1）= a（2m）= a（2m-1）+ a（m）$ ，使用 $ a（0）= a（1）= 1 $ 。您可以禁用 $ a（n）= t（n + 1）$ 。的确：

• 如果 $ n= 2m + 1 $ 那么 $$ t（n + 1）= t（2m + 2 ）= t（m + 1）+ t（2m）= a（m）+ a（2m-1）= a（2m）= a（2m + 1）= a（n）。$$ < / li>
• 如果 $ n= 2m $ 那么 $$ t（n + 1）= t（2m + 1）= t（m + 1）+ t（2m-1）= a（m）+ a（2m-2）= a（m）+ a（2m-1）= a（2m）= a（n）。$$