003【算法篇】时间复杂度基础知识

首先我们要明确一点，在编程领域中我们需要考虑的因素很多，算法性能只是其一，甚至不能算是最优先考虑的因素，人们往往更优先考虑的方面包括：正确性、健壮性、可维护性、界面交互体验等等。但是为什么我们又要一而再强调算法？

有种观点是，算法是编程领域的「通用货币」，即：为了追求某种更需要优先考虑的因素，而需要支付的代价。怎么样理解呢？比如大家都知道C语言比Java语言的性能强至少3倍，但是由于Java语言的平台通用性、异常处理机制等诱人的feature，现如今的商业项目往往会选择Java作为开发语言，而不是C语言，而为了弥补这3倍的性能差异，所以必须支付一定的代价以维持较好的性能，也即重视编程算法。

如果程序的运行环境、编程语言等各方面针对同一段程序无显著差异、存储空间无限大、CPU性能无限高，又何须劳神费力去研究算法性能？

记号𝛩

𝛩记号表示时间复杂度的渐近紧接界，简单来说就是近似刻画一个程序算法的时间复杂度函数。既然是函数，那我们就必须给出它在数学逻辑上的严格定义：

𝛩(g(n))表示如下函数的集合：
𝛩(g(n)) = { f(n)：存在正常量 $c_1$ 、 $c_2$ 和 $n_0$ ，使得对所有 $n \geq n_0$ ，有 $0 \lt c_1g(n) \leq f(n) \leq c_2g(n)$ }

画图表示可能更为清晰，如下图所示：

image-20200128204019199.png

跟平常我们学的极限是否有亲切感？

注意到f(n)表示一个集合，也就是说程序的时间复杂度可能不是确定的值，而是某一类值的函数集合。这也是必然，例如同样的插入排序针对输入规模的不同、已排序程度的不同呈现出不同的时间复杂度，例如：已经是升序的输入序列、已经是降序的输入序列其时间复杂度是不一致的

我们再举个例子予以更清晰的认识，假设我们设计了某个程序，经过计算它的时间复杂度：
$T(n) = \frac{1}{2}n^2-3n\tag{1}$
则根据我们以往的经验，立马可以认为T(n)=𝛩( $n^2$ )。直觉很重要，但是我们还是应该给予严格的数学证明，按上述的数学定义，假设我们认定T(n)=𝛩( $n^2$ )，那我们来个数学验证，很容易根据(1)式得到如下的公式，即存在正常量 $c_1$ 、 $c_2$ 和 $n_0$ ，使得对所有 $n \geq n_0$ ，有：
$c_1n^2 \leq \frac{1}{2}n^2-3n \leq c_2n^2\tag{2}$
对(2)两边除以 $n^2$ ，可得如下公式：
$c_1 \leq \frac{1}{2}-\frac{3}{n} \leq c_2\tag{3}$
很明显为使右式成立，只需要 $c_2\geq1/2$ ，即可对所有的n有效；为使左式成立，则需要 $c_1\leq1/14$ ，则可对任何 $n\geq7$ 的值有效，由此我们可以说：当 $c_1\leq1/14$ ， $c_2\geq1/2$ ，且 $n\geq7$ 时可以证明 $\frac{1}{2}n^2-3n = 𝛩(n^2)$ 。当然常量的取值还存在其它选择。