前言
算法分析是对一个算法需要多少计算时间和存储空间作定量分析。此文主要介绍如何使用渐近分析记号来表示算法的时间复杂度以及如何对算法效率进行比较。
分析涉及的概念
-
输入规模度量
- 算法的时间效率和空间效率都用输入规模的函数进行度量
- 对相同大小的输入实例具有相同的分析结果
- 对于所有的算法，对于规模更大的输入都需要运行更长的时间
- 经常使用一个输入规模\(n\)为参数的函数来研究算法效率
-
运行时间的度量单位
-
用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率
-
基本操作通常是算法最内层循环中最费时的操作
-
算法运行时间的估计
\[T(n) \approx c_{op}C(n) \]- \(n\)是算法的输入规模
- \(c_{op}\)是特定计算机中一个算法基本操作的执行时间
- \(C(n)\)是该算法需要执行的基本操作的次数
-
-
算法的最优、最差和平均效率
- 最差效率是指输入规模为\(n\)时，算法在最坏情况下的效率
- 最优效率是指输入规模为\(n\)时，算法在最优情况下的效率
- 平均效率是指在"典型"或"随机"输入的情况下，算法具有的行为（效率）
小规模输入在运行时间上的差别不足以将高效算法和低效算法区分开来。一个需要指数级操作次数的算法只能用来解决规模非常小的问题。
指数增长是恐怖的，例如\(n^2\)和\(2^n\)，当规模增加一倍，\(n \to 2n\)，那么对于\(n^2\)来说，运行时间只是增加4倍，而对于\(2^n\)来说，却是增加了\(2^n\)倍，这个倍数与n有关。
渐近表达式
常数间的差异较小，在表示算法时间复杂度时我们通过省略常数对表达式的影响，如：\(100n^2\)、\(1.5n^2\)、\(n^2+4\)、\(10n^2-3n+6\)，我们都看成是相等的。
- 渐近表达式的核心内容就是忽略常数。
- 渐近表达式是一个被大家认同的计算机里表示运行时间和空间的方法。是另一个数学系统，和精确数学、模糊数学以及近似数学都不相同。
渐近分析的符号
算法效率的主要指标是基本操作次数的增长次数。为了对这些增长次数进行比较和归类，计算机科学家们使用了3种符号：
- \(O\) 上界
- \(\Omega\) 下界
- \(\Theta\) 近似
渐近上界符\(O\)
存在正常数\(c\)和\(n_0\)，使得对所有\(n \ge n_0\) ，有
\[f(n) \le cg(n) \]记为\(f(n) \in O(g(n))\)
如，\(n \in O(n^2)\) ，\(100n+5 \in O(n^2)\)，\(n(n-1)/2 \in O(n^2)\)
渐近下界符\(\Omega\)
存在正常数\(c\)和\(n_0\)，使得对所有\(n \ge n_0\)，有
\[f(n) \ge cg(n) \]记为\(f(n) \in \Omega(g(n))\)
如，\(n^3 \in \Omega(n^2)\)，\(n(n+1) \in \Omega(n^2)\)，\(4n^2+5 \in \Omega(n^2)\)
渐近近界符\(\Theta\)
存在正常数\(c_1\)，\(c_2\)和\(n_0\)，使得对所有\(n \ge n_0\)，有
\[c_2g(n) \le f(n) \le c_1g(n) \]记为\(f(n) \in \Theta(g(n))\)
如，\(n^2+3n+2 \in \Theta(n^2)\)，\(n(n-1)/2 \in \Theta(n^2)\) ，\(4n^2+5 \in \Theta(n^2)\)
渐近符号的有用特性
定理：如果\(t_1(n) \in O(g_1(n))\) 并且\(t_2(n) \in O(g_2(n))\) ，则
\[t_1(n)+t_2(n) \in O(max\{g_1(n), g_2(n)\}) \]对于符号\(\Theta\)和\(\Omega\)，该定理也成立。该定理表示：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。
在渐近分析种等号的滥用
我们使用\(f(n)=O(g(n))\)来表示\(f(n)\)是\(O(g(n))\)的一个成员函数，而不用传统的\(f(n) \in O(g(n))\)来表示，是因为习惯问题。
例如，\(f(n)=5n^3；g(n)=3n^2；f(n)=O(n^3)=g(n)\) 但是\(f(n) \ne g(n)\)
因此，\(f(n)=\Theta(g(n))\)的确切意义是：\(f(n) \in \Theta(g(n))\)。一般情况下，\(\Theta(g(n))\)表示的是\(\Theta(g(n))\)中的某个函数。如，\(2n^2+3n+1=2n^2+\Theta(n)\) 表示\(2n^2+3n+1=2n^2+f(n)\)，其中\(f(n)\)是\(\Theta(n)\)中某个函数。
渐近分析记号的若干性质
-
传递性
-
反身性
-
对称性
\(f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))\)
-
互对称性
\(f(n)=O(g(n)) \Leftrightarrow g(n)=\Omega(f(n))\)
\(f(n)=o(g(n)) \Leftrightarrow g(n)=\omega(f(n))\)
-
算术运算
\(f(n)+g(n)=O(max\{f(n),g(n)\})\)；
\(f(n)+g(n)=O(f(n)+g(n))\)；
\(f(n)*g(n)=O(f(n)*g(n))\)；
\(cf(n)=O(f(n))\)；
\(g(n)=O(f(n)) \Rightarrow g(n)+f(n)=O(f(n))\)；
算法效率的比较
基本的效率类型
常数\(C\) < 对数\(logn\) < \(log^2n\) < 线性\(n\) < \(nlogn\) < 平方\(n^2\) < 立方\(n^3\) < 指数\(2^n\) < 阶乘\(n!\) < \(n^n\)
最常用的关系式
- 多项式：\(a_0 + a_1n + a_2n^2+...+a_dn^d = \Theta(n^d)\) ，其中 \(a_d > 0\)
- 对数：\(log_an=\Theta(log_bn)\)，其中\(a，b>0\)为常数。（我们不区分底数是2还是10）
- 对数：对任意\(a,b>0,(logn)^a=O(n^b)\) （需要注意，b可以是小数）
- 指数：对任意\(r>1\)和\(d>0\)，\(n^d=O(r^n)\)
基本效率类型举例
-
线性时间 \(O(n)\)
运行时间只是输入大小的一个常数倍数。
如，求n个数中最大数问题；合并两个有序的序列；
-
\(O(nlog(n))\)时间
\(O(nlog(n))\)时间多出现在分治算法中。如合并排序、堆排序都将产生\(O(nlog(n))\)时间。
-
平方时间 \((O^2)\)
如，列举所有元素对；求平面上n个点中最近的两个点之间的距离。
-
多项式时间 \(O(n^k)\)
-
指数时间
最大独立集问题：给出一个图，求最大的一个点集使得其中任何两个点都不存在一条边。穷举搜索产生运行时间\(O(n^22^n)\)的算法。
渐近增长率比较的三种方法
-
定义法
找到正常数\(c\)和\(n_0\)使得对所有\(n\ge n_0\)，有\(f(n) \le cg(n)\)，则\(f(n)=O(g(n))\)
-
极限法，若
\[\lim\limits_{n \to \infty }{\frac{f(n)}{g(n)}=0} \]则，\(f(n)=O(g(n))\).
-
前两种情况意味着 \(t(n) \in O(g(n))\)
-
后两种情况意味着 \(t(n) \in \Omega(g(n))\)
-
第二种情况意味着 \(t(n) \in \Theta(g(n))\)
-
取对数法
对于比较难比较的两个数，我们可以先对它们同时取对数后进行比较。但是要注意，取完对数后的常数是不能忽略的。
小结
开学三个月后，终于有时间写博客了~