渐进符号定义介绍

备考初赛。为了方便记忆，给出如下定义：

对于 $f(n)=\Theta(g(n))$，我们恰可以用 $g(n)$ 乘上两个非 $0$ 常数分别拟合出 $f(n)$ 的上下界（可以取等号）。
对于 $f(n)=\Omicron(g(n))$，我们仅可以用 $g(n)$ 乘上一非 $0$ 常数分别拟合出 $f(n)$ 的上界（可以取等号）。
对于 $f(n)=\Omega(g(n))$，我们仅可以用 $g(n)$ 乘上一非 $0$ 常数分别拟合出 $f(n)$ 的下界（可以取等号）。

实际运用 $\Theta,\Omicron$ 较多，毕竟只能知道下界你还跑什么程序。（？）

需要注意：

$\forall a\neq 1,\log_a n=\Omicron(\log_2 n)$，因此复杂度分析中对数底数一般不写。
实际上许多选手在时间复杂度分析时会直接写 $O$ 而不是 $\Omicron$ 即 $\text{Omicron}$ 符号，毕竟好打很多。而且多数我们遇到的题目在 LCT 的势能分析还有势能线段树等场景下，我们的复杂度分析都只能给出上界，毕竟复杂度的影响因素还有实际操作与数据，这也包括某些根号题。

注意此处给出例子线段树合并这一 trick 实际上是有下界的，即一条链且每个线段树单点操作相同情况，所以应该也能用 $\Theta$ 符号。

主定理

用于求解一类递归问题的复杂度。

\[T(n)=aT(\frac{n}{b})+f(n) \]

\[T(n)= \begin{cases} \Theta(n^{\log_b a}) & f(n)=\Omicron(n^{\log_b a-\epsilon}),\epsilon > 0\\ \Theta(f(n)) & f(n)=\Omega(n^{\log_b a+\epsilon}),\epsilon\geq 0\\ \Theta(n^{\log_b a}\log^{k+1} n) & f(n)=\Theta(n^{\log_b a}\log^k n),k\geq 0\\ \end{cases} \]

且第二种情况应有 $af(n)\le cf(\frac{n}{b})$，$n$ 足够大且 $\exist c<1$ 满足该条件。

一句话记忆：计算 $\log_b a$，如果 $f(n)$ 与 $n^p$ 有关的部分可以被 $n^{\log_b a}$ 完全覆盖，对数强相关总复杂度多一个 $\log$。否则考虑对于 $n^p$ 有关部分找到的是上界还是下界，上 $n^{\log_b a}$，下 $f(n)$。

资讯详情

（简记）时间复杂度分析 $\Omicron,\Theta,\Omega$ 的区别

渐进符号定义介绍

主定理