算法复杂度初探

研究算法，研究什么？

算法的原理：即此算法为何被提出来，其解决问题的原理是什么
算法的复杂度：即此算法快不快，有多快；需要的额外空间是多少，大不大。

而在研究之前，首先应知道相关基础知识。

算法分析是理论研究，是关于计算机程序性能和资源利用的研究。

Q：既然算法与计算机程序性能有关，那么性能就必须放在第一位吗？

A：对于有些问题的处理方案（即算法），以现在的技术，在计算机上进行运算或者处理，但时间是无限久远的，或者无法在短时间内解决，这时候就应该将算法置于首位，提升算法解决问题的速度。

对于有些问题，已有的算法已经能够在短时间解决问题，那么算法就不应该被摆在第一位，那么这时就会考虑其他因素：成本，简洁度，安全性，稳定度等等。

我们向往速度，所以我们总是在追求速度——更快的交通，更快的网络。或许这也是为什么算法会吸引这么多人学习的原因吧！

符号说明

$O(g(n))$ 大 $O$ 符号，表示复杂度的上限为 $g(n)$ 的 $c$ 倍（ $c$ 为常数）
$\Omega (g(n))$ 大 $\Omega$ 符号，表示复杂度的下限为 $g(n)$ 的 $c$ 倍（ $c$ 为常数）
$\Theta (g(n))$ 大 $ $ 符号，表示复杂度的介于 $c_1 g(n)$ 于 $c_2g(n)$ 之间（ $c_1 c_2$ 为常数）

从排序入手

输入一组数 $(a_{1} a_{2} , ...... , a_{n})$

按需求重新排列后进行输出 $( a_{1}^{'} a_{2}^{'} , ...... , a_{n}^{'} )$

使得 $a_{1}^{'} \le a_{2}^{'} \le ...... \le a_{n}^{'}$ （使得大小单调递增）

插入排序

伪代码为：

Insertion Sort(A,n)	// Sorts A[1 , 2 , ...... , n]
 for j <-- 2 to n
 	do key <-- A[j]
    	i <-- j-1
    	while i > 0 and A[i] > key
    		do A[i+1] <-- A[i]
    			i <-- i-1
    		A[i+1]<-- key

顾名思义，该算法核心在于插入，从第二个数起开始插入，也就是上述伪码中的 j ，根据程序的运行可知，a[j] 之前的数均已经排序完成，所以只需不断插入即可！

运行时间

输入的数据本身（如输入已经有序，那么进行的步骤将会非常少）
输入数据的规模（六百万数据和六亿数据运行的时间肯定不一样） ---- 我们将输入数据的规模进行参数化，之后将运行时间看作是待排列数据规模的函数
硬件设备的种类（同样的算法在PC 和超级计算机运行情况不同）

一般研究种类

最坏情况（最常研究的）

---- T(n) = 输入规模为n时的最长运行时间
平均情况（有时研究）

---- T(n) = 输入规模之下的所有可能期望时间 （也就是一种加权平均，即每种输入的运行时间乘以那种输入出现的概率）但是输入出现的概率是不知道的，所以需要进行假设，如每种输入出现的概率相等。
最好情况（假象 bogus：因为最好的情况往往不会出现，但可以骗人，有些算法对于特定的数据可能会有超级优秀的速率，但是这不具有普遍性，是无效的）

插入排序的最坏运行时间

由于不同设备因其性能不同，运行时间也会不同，那我们如何比较算法的运行时间呢？ ---- 通常，我们比较算法时，比较的是其相对速度，即两个算法在同一机器上的时间。

但是一个算法一定会在所有计算机上都是优秀的吗？ ---- 算法的BIG IDEA ! —— Asymptotic analysis

Asymptotic analysis

忽略掉依赖于机器的常量，也就是不同机器对于算法的影响一般仅仅相当于时间的n倍
不是去检查实际的运行时间，而是去关注运行时间的增长 ---- look at growth of T(n) as n --> $$

Asymptotic notation

$\theta$ ：弃去公式的低阶项，并忽略前面的常数因子 Ex：公式为： $3{n}^{3}+90{n}^{2}-5n+6046$ = $\theta$ (${n}^{3}$)
当 $n$ --> $$ 时 , $\theta$ (${n}^{2}$) 的算法迟早会战胜一个$\theta$ (${n}^{3}$)的算法

Insertion Sort analysis

最坏情况：即输入的数已经按照从大到小排列好 ---- T(n) = $\sum\limits_{j=2}^{n}{\theta (j)=\theta ({n}^{2})}$ 也就是一个常数级数

由上可见：当数据量小的时候，插入排序的速度是毋庸置疑的，但数据量大的时候，就不是那么快了

归并排序

伪码

Merge Sort A[1 , 2 , ... , n]
1. if n = 1 , done
2. Recursively sort 
   A[1 , 2 , ..., [n/2]]
   A[[n/2]+1 , ... , n]
3. Merge 2 sort lists

$T_{1}$ = $\theta$ (1) // 滥用 $\theta$

$T_{2}$ = 2T(n/2) // 拆成两个数列（故乘2），每个是(n/2)个数

$T_{3}$ = $\theta$ (n) // 将两个排好的数列进行归并，复杂度与输入规模成线性关系

\[ T(n) = \left\{ \begin{array}{ll} \theta (1) & \textrm{if $ n=1 $}\\ 2T(\frac{n}{2})+\theta(n) & \textrm{if $n > 1$}\\ \end{array} \right. \] 采用递归树方法进行分析 T(n) = $2T(\frac{n}{2}) + cn$ (用 $cn$ 替换了$\theta$(n) )，如图：