标签：ba 定理 quad mathcal operatorname log
- 主定理：将一个规模为 n 的问题，分治成 a 个\(\lceil\dfrac{n}{b}\rceil\)的子问题，每次带来的额外计算为 \(\mathcal{O}(n^d)\),可得到以下关系式：
\[T(n)=aT(\lceil\dfrac{n}{b}\rceil)+\mathcal{O}(n^d)
\]
\[(\text{for \,constants\,}a>0,b>1,d\ge0),\text{then}:
\]
\[T(n) = \begin{cases} \mathcal{O(n^d)} & if\quad d>\operatorname{log}_ba\\ \mathcal{O(n^d\operatorname{log}n)} & if\quad d=\operatorname{log}_ba\\ \mathcal{O(n^{\operatorname{log}_ba})} & if\quad d<\operatorname{log}_ba\\ \end{cases}
\]
标签：ba,
定理,
quad,
mathcal,
operatorname,
log
From： https://www.cnblogs.com/AC7-/p/16813697.html