时间复杂度分析

五种时间复杂度符号和数学定义

1. 大 O 符号（O）：若 $\exists{c, n_{0}} \in \mathbb{R}^{+}$，使得 $\forall{n} > n_0$，$f(n) \leq cg(n)$，则 $f(n) = O(g(n))$。
2. 小 o 符号（o）：若 $\forall{c} > 0$，$\exists{n_0}$，使得 $\forall{n} > n_0$，$f(n) < cg(n)$，则 $f(n) = o(g(n))$。
3. 大 Omega 符号（Ω）：若 $\exists{c, n_{0}} \in \mathbb{R}^{+}$，使得 $\forall{n} > n_0$，$f(n) \geq cg(n)$，则 $f(n) = \Omega(g(n))$。
4. 小 omega 符号（ω）：若 $\forall{c} > 0$，$\exists{n_0}$，使得 $\forall{n} > n_0$，$f(n) > cg(n)$，则 $f(n) = \omega(g(n))$。
5. Theta 符号（θ）：若 $\exists{c_1, c_2, n_0} \in \mathbb{R}^{+}$，使得 $\forall{n} > n_0$，$c_1g(n) \leq f(n) \leq c_2g(n)$，则 $f(n) = \Theta(g(n))$。可以理解为当上界和下界的复杂度都是同一增长量时，那么这个复杂度也称为紧确界。

以下是关于这些记号的含义和通俗理解的表格：

记号	含义	通俗理解
Θ	紧确界	相当于"="
O	上界	相当于"<="
o	非紧的上界	相当于"<"
Ω	下界	相当于">="
ω	非紧的下界	相当于">"

这些记号用于描述算法的时间复杂度的渐近行为，帮助我们了解算法的性能特征。

平均、最好和最坏时间复杂度

时间复杂度一般用于不同算法之间相互比较，比如冒泡排序、插入排序、堆排序。但是，对于同一算法内部，输入值的情况不同，也可以分为平均、最好和最坏时间复杂度。比如二叉搜索树，退化成链表的单支树和平衡树的查找时间复杂度也不相同。

平均、最好和最坏复杂度是描述算法性能的不同方面，它们的数学定义如下：

平均时间复杂度：平均时间复杂度是对算法在所有可能输入情况下的运行时间进行加权平均的度量。设 $T(n)$ 是算法在输入规模为 $n$ 时的运行时间，则平均时间复杂度 $\bar{T}(n)$ 定义

$$\bar{T}(n) = \sum_{i=1}^{k} p_i \cdot T_i(n)$$

其中，$T_i(n)$ 是在第 $i$ 种输入情况下的运行时间，$p_i$ 是第 $i$ 种情况出现的概率，$k$ 是可能的输入情况的总数。

最好时间复杂度：最好时间复杂度是在最理想情况下的运行时间，即算法执行时所需的最小时间。最好时间复杂度通常用于描述算法的最优情况。数学上没有一个统一的定义，通常是直接给出算法在最好情况下的运行时间的表达式。

最坏时间复杂度：最坏时间复杂度是在最不利情况下的运行时间，即算法执行时所需的最大时间。最坏时间复杂度通常用于描述算法的最坏情况。最坏时间复杂度的定义如下：

$$T_{\text{worst}}(n) = \max_{\text{input size}} T(n)$$

其中，$T_{\text{worst}}(n)$ 是最坏情况下的运行时间，$T(n)$ 是算法在输入规模为 $n$ 时的运行时间。