论文标题
划分和诱使复发分裂的身份和周期性振荡
Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
论文作者
论文摘要
我们研究形式\ begin {equation*}的分裂和互动复发 f（n） =αf（\ lfloor \ tfrac n2 \ rfloor） +βf（\ lceil \ tfrac n2 \ rceil） + g（n）\ qquad（n \ ge2），\ end {equation*}，给定$ g（n）$和$ f（1）$，其中$α，β\ ge0 $带有$α+β> 0 $;这种复发经常出现在计算机算法，计算系统，组合序列和相关领域的分析中。我们表明，该解决方案始终满足简单\ emph {Identity} \ begin {equation*} f（n） = n^{\ log_2（α+β）} p（\ log_2n） - q（n）\ end \ end {equation*}在$ g（n）$上的optimum（iff）条件下。这种形式不仅是一种身份，而且是渐近扩展，因为$ q（n）$的订单较小。提供了定期功能$ p $的\ emph {Continuity}的显式表单，以及其他一些平滑度属性。我们展示了如何轻松地将结果应用于从文献中收集的数十个具体示例，以及如何向各个方向扩展它们。我们的证明方法令人惊讶地简单且基本，但是对于我们理论适用的所有示例的结果都会带来最强类型的结果。
We study divide-and-conquer recurrences of the form \begin{equation*} f(n) = αf(\lfloor \tfrac n2\rfloor) + βf(\lceil \tfrac n2\rceil) + g(n) \qquad(n\ge2), \end{equation*} with $g(n)$ and $f(1)$ given, where $α,β\ge0$ with $α+β>0$; such recurrences appear often in analysis of computer algorithms, numeration systems, combinatorial sequences, and related areas. We show that the solution satisfies always the simple \emph{identity} \begin{equation*} f(n) = n^{\log_2(α+β)} P(\log_2n) - Q(n) \end{equation*} under an optimum (iff) condition on $g(n)$. This form is not only an identity but also an asymptotic expansion because $Q(n)$ is of a smaller order. Explicit forms for the \emph{continuity} of the periodic function $P$ are provided, together with a few other smoothness properties. We show how our results can be easily applied to many dozens of concrete examples collected from the literature, and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary, but leads to the strongest types of results for all examples to which our theory applies.
