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

严谨定义请前往OI-wiki

渐进符号定义介绍

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

• 对于 \(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\) 较多，毕竟只能知道下界你还跑什么程序。（？）

需要注意：

1. \(\forall a\neq 1,\log_a n=\Omicron(\log_2 n)\)，因此复杂度分析中对数底数一般不写。

2. 实际上许多选手在时间复杂度分析时会直接写 \(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)\)。