没有证明绝对不是因为我不会，证明可看:重谈主定理（master定理）及其证明
这篇文章主要是写给自己看的，写的不好。
\[\text{如果有} T(n)=aT(\lceil\frac{n}{b}\rceil)+O(n^d) \]\[\text{其中}n\text{问题规模，}a\text{为递推子问题数量，}\frac{n}{b}\text{为每个子问题的规模，}f(n)\text{为递推以外进行的计算工作。} \]\[\text{那么有：} \]\[T(n)=\begin{cases} O(n^d) & \text{如果} d>\log_ba \\ O(n^d \log n) & \text{如果} d=\log_ba \\ O(n^{\log_ba}) & \text{如果} d<\log_ba \end{cases} \]怎么记忆呢？聪明的我用了chatgpt生成记忆方法如下：
为了记忆主定理公式，我建议采用以下步骤：
Step 1: 写下主定理公式的基本形式： $$T(n)=aT(\lceil\frac{n}{b}\rceil)+O(n^d)$$
Step 2: 确定每个参数的含义：
- \(n\)：问题的规模
- \(a\)：递归子问题的数量
- \(\frac{n}{b}\)：每个递归子问题的规模
- \(d\)：递归以外的计算工作的时间复杂度
Step 3: 按照\(d\)与\(\log_ba\)的关系分类讨论：
情况1: 如果\(d > \log_ba\)，则递归以外的计算工作占据主导地位，因此时间复杂度为\(O(n^d)\)。
情况2: 如果\(d = \log_ba\)，则递归和递归以外的计算工作对时间复杂度的贡献相当，因此时间复杂度为\(O(n^d \log n)\)。
情况3: 如果\(d < \log_ba\)，则递归的规模增长速度占主导地位，因此时间复杂度为\(O(n^{\log_ba})\)。
Step 4: 将所有情况整合到一起，形成最终的记忆公式：
\[T(n)=\begin{cases} O(n^d) & \text{如果} d>\log_ba \\ O(n^d \log n) & \text{如果} d=\log_ba \\ O(n^{\log_ba}) & \text{如果} d<\log_ba \end{cases} \]通过按照这些步骤记忆和理解主定理公式，您将能够轻松地计算和推导出递归算法的时间复杂度。
标签：ba,递归,text,定理,证明,log,复杂度,但是 From： https://www.cnblogs.com/znpdco/p/17637016.html