lol
by Wilting @ 2024-09-20 10:27:42
@[Hagasei](/user/383785) 我觉得 `Chat GPT` 说得挺好的啊
># 主定理（Master Theorem）
>
>主定理是一个用于解决递归关系的强有力工具，常用于分析分治算法的时间复杂度。它为特定形式的递归关系提供了简洁的解决方案。
>
>## 递归关系形式
>
>主定理通常应用于以下形式的递归关系：
>
>\[
>T(n) = aT\left(\frac{n}{b}\right) + f(n)
>\]
>
>其中：
>- \(a \geq 1\) 是子问题的数量。
>- \(b > 1\) 是每个子问题的规模因子。
>- \(f(n)\) 是分治算法中合并子问题所需的时间。
>
>## 主定理的情况
>
>根据 \(f(n)\) 与 \(n^{\log_b a}\) 的关系，主定理分为三种情况：
>
>1. **情况 1**：如果 \(f(n) = O(n^{\log_b a - \epsilon})\)（对于某个 \(\epsilon > 0\)），那么：
> \[
> T(n) = \Theta(n^{\log_b a})
> \]
>
>2. **情况 2**：如果 \(f(n) = \Theta(n^{\log_b a})\)，那么：
> \[
> T(n) = \Theta(n^{\log_b a} \log n)
> \]
>
>3. **情况 3**：如果 \(f(n) = \Omega(n^{\log_b a + \epsilon})\)（对于某个 \(\epsilon > 0\)），并且 \(a f\left(\frac{n}{b}\right) \leq c f(n)\) 对于某个常数 \(c < 1\) 和足够大的 \(n\) 成立，那么：
> \[
> T(n) = \Theta(f(n))
> \]
>
>## 使用注意
>
>使用主定理时，需要确保满足相应的条件，以便正确应用。主定理的优势在于它能快速给出时间复杂度的结果，而不必深入到递归的细节中去。
>
by Wilting @ 2024-09-20 10:48:17
~~我怎么记得主定理是主=6呢~~
by tmp_get_zip_diff @ 2024-09-20 12:58:47