Data Structures Algorithms 简明教程
Data Structures - Asymptotic Analysis
Asymptotic Analysis
算法的渐近分析是指对其运行时性能定义数学基础/框架。使用渐近分析，我们能很好地得出算法的最佳情况、平均情况和最差情况。
渐近分析是输入绑定的，即，如果算法没有输入，则推断算法以常数时间运行。除了“输入”，所有其他因素都被当作常数。
渐近分析是指用计算的数学单位计算任何操作的运行时间。例如，一个操作的运行时间计算为 f(n)，而另一个操作的运行时间可能计算为 g(n2)。这意味着随着 n 的增加，第一个操作的运行时间将线性增加，而当 n 增加时，第二个操作的运行时间将呈指数增加。类似地，如果 n 很小，则两个操作的运行时间将几乎相同。
通常，算法所需的时间分为以下三种类型−
-
Best Case − 程序执行所需的最短时间。
-
Average Case − 程序执行所需的平均时间。
-
Worst Case − 程序执行所需的最长时间。
Asymptotic Notations
算法的执行时间取决于指令集、处理器速度、磁盘 I/O 速度等。因此，我们渐近估计算法的效率。
算法的时间函数表示为 T(n) ，其中 n 是输入大小。
使用不同类型的渐近标记来表示算法的复杂度。以下渐近标记用于计算算法的运行时间复杂度。
-
O − 大 O 标记
-
Ω − 大欧米茄标记
-
θ − 大西塔标记
-
o − 小 o 标记
-
ω − 小欧米茄标记
Big Oh, O: Asymptotic Upper Bound
标记 Ο(n) 是表达算法运行时间上界的正式方法。是最常用的标记。它测量算法可能完成的最长时间或 worst case time complexity 。
一个函数 f(n) 可以表示为 g(n) 的阶，即 O(g(n)) ，如果正整数 n 的一个值存在为 n0 ，正常数 c 满足 −
对于所有情况，当 $n > n0$ 时，$f(n)\leqslant c.g(n)$。
因此，函数 g(n) 是函数 f(n) 的上界，因为 g(n) 比 f(n) 增长得更快。
Big Omega, Ω: Asymptotic Lower Bound
符号 Ω(n) 是形式化地表示算法运行时间的下界的形式。它度量算法可能花费的@\( best case time complexity \)或完成操作的最佳时间量。
当存在常量@\( c \) 时，使对所有足够大的@\( n \)的值都有 $f(n)\geqslant c.g(n)$，则称 $f(n) = \Omega (g(n))$。其中@\( n \) 是正整数。这意味着函数@\( g \)是函数@\( f \)的下界；在大于@\( n, f \)的某些值之后，永不会低于@\( g \)之。
Theta, θ: Asymptotic Tight Bound
符号 θ(n) 是形式化地表示算法运行时间的下界和上界的形式。一些人可能会混淆 theta 符号与平均情况时间复杂度；尽管大 theta 符号可以几乎精确地用于描述平均情况，但其他符号也可以使用。
当存在常量@\( c1 \) 和@\( c2 \) 使对所有足够大的@\( n \)的值都有 $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$，则称 $f(n) = \theta(g(n))$。其中@\( n \) 是正整数。
这意味着函数@\( g \)是函数@\( f \)的紧束缚。
Little Oh, o
@\( O-notation \) 提供的渐近上界可能是渐近紧的，也可能不是渐近紧。束缚 $2.n^2 = O(n^2)$ 是渐近紧的，但束缚 $2.n = O(n^2)$ 不是。
我们使用@\( o-notation \) 来表示不是渐近紧的上界。
我们正式定义@\( o(g(n)) \)（g(n) 的小 o）为对任何正的常量 $c > 0$，且存在一个值 $n_{0} > 0$，使得 $0 \leqslant f(n) \leqslant c.g(n)$ 的集合@\( f(n) = o(g(n)) \)。
直观地说，在@\( o-notation \)，随着@\( n \) 接近无穷大，函数@\( f(n) \) 相对于@\( g(n) \) 变得无关紧要；即，
\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0
Little Omega, ω
我们使用 ω-notation 来表示一个渐近不严格的下界。然而，我们正式定义 ω(g(n)) （g(n) 的小欧米茄）为集合 f(n) = ω(g(n)) ，对于任何正常数 C > 0 和值 $n_{0} > 0$，都有 $0 \leqslant c.g(n) < f(n)$。
例如，$\frac{n^2}{2} = \omega (n)$，但 $\frac{n^2}{2} \neq \omega (n^2)$。关系 $f(n) = \omega (g(n))$ 暗示存在以下极限
\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty
也就是， f(n) 相对于 g(n) 会变得任意大，因为 n 趋近于无穷大。