数据结构和算法分析

问题引出

假设有一道题目：有一组N个数而要确定其中第k个最大者，我们称之为选择问题，那么这个程序如何编写？最直观地，至少有两种思路：

1、将N个数读入一个数组中，再通过某种简单的算法，比如冒泡排序法，以递减顺序将数组排序，则第k个位置上的元素就是我们需要的元素

2、稍微好一些的做法，将k个元素读入数组并以递减顺序排序，接着将接下来的元素再逐个读入，当新元素被读到时，如果它小于数组中的第k个元素则忽略之，否则将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组，当算法终止时，位于第k个位置上的元素作为答案返回

这两种算法都很简单，但是假设我们有一千万个元素的随机文件和k=5000000进行模拟将发现，两个算法尽管最终都可以给出正确答案，但是在合理时间内均无法结束。因此，这两种算法都不能被认为是好的算法，因为从实际角度出发，它们无法在合理的时间内处理输入的数据。

数据结构和算法分析的提出

在许多问题中，一个很重要的观念是：写出一个工作程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题，我们将在接下来的文章中看到对于大量的输入如何估计程序的运行时间，尤其是如何在未具体编码的情况下比较两个程序运行的时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法，这些方法将使得我们能够发现需要我们集中精力努力优化的那些代码段。

那么，首先，先了解一下什么是数据结构和算法分析（特别指出，后文的例子均以Java代码编写）。

数据结构

数据结构是计算机存储、组织数据的方式，是指数据相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率（这就是为什么我们要研究数据结构的原因），数据结构往往同高效的检索算法和索引技术相关。

常见的数据结构有数组、栈、队列、链表、树、散列等，这些数据结构将是本数据结构的分类中重点研究的对象。

算法分析

算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。对于一个问题，一旦某种算法给定并且（以某种方式）被确定是正确的，那么重要的异步就是确定该算法将需要多少注入时间或空间等资源量的问题。如果：

1、一个问题的求解算法竟然需要长达一年时间，那么这种算法就很难有什么用处

2、一个问题需要若干个GB的内存的算法，在当前大多数机器上也是无法使用的

数学基础

无论是数据结构还是算法分析，都用到了大量的数学基础，下面将这些数学的基础简单总结一下：

1、指数

（1）X^AX^B = X^A+B

（2）X^A/X^B = X^A-B

（3）(X^A)^B = X^ABsi

（4）X^N + X^N = 2X^N ≠ X^2N

（5）2^N + 2^N = 2^{N + 1}

2、对数

（1）X^A = B当且仅当log_xB = A

（2）log_AB = log_CB / log_CA

（3）logAB = logA + logB，A>0且B>0

3、级数

（1）∑2ⁱ = 2^N+1 - 1

（2）∑Aⁱ = (A^N+1 - 1) / (A - 1)，若0<A<1，则有∑Aⁱ ≤ 1 / (1 - A)

4、模运算

如果N整除A、N整除B，那么就说A与B模N同余，记为A≡B(mod N)。直观地看，这意味着无论是A还是B被N去除，所得余数都是相同的，于是假如有A≡B(mod N)，则：

（1）A + C ≡ B + C(mod N)

（2）AD ≡ BD (mod N)

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数，时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数，使用这种方式时，时间复杂度可被称为是渐进的，他考察当输入值大小趋近无穷时的情况。

那么首先先看一个简单的例子，这里是计算Σi³的一个简单程序片段：

1 public static void main(String[] args)
 2 {
 3 System.out.println(sum(5));
 4 }
 5 
 6 public static int sum(int n)
 7 {
 8 int partialSum;
 9 
10 partialSum = 0;
11 for (int i = 0; i <= n; i++)
12 partialSum += i * i * i;
13 
14 return partialSum;
15 }

对这个程序片段的分析是简单的：

1、声明不记入时间

2、第10行和都14行各占一个时间单元

3、第12行每次执行占用4个时间单元（两次乘法、一次加法和一次赋值），而执行N次共占用4N个时间单元

4、第11行在初始化i，测试i≤n和对i的自增都隐含着开销，所有这些总开销是初始化1个时间单元，所有的测试为N+1个时间单元，所有自增为N个时间单元，共2N+2个时间单元

忽略调用方法和返回值的开销，得到总量是6N+4个时间单元，按照最开始的定义不包括这个函数的低阶项和首项系数，因此我们说该方法的时间复杂度是O(N)。继而，我们顺便得出若干个一般法则：

法则一----for循环

一个for循环的运行时间至多是该for循环内部那些语句（包括测试）的运行时间乘以迭代的次数，因此假如一个for循环迭代N次，那么其时间复杂度应该为O(N)

法则二----嵌套for循环

从里向外分析这些循环，在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积，因此假如有以下代码：

1 public static int mutliSum(int n)
 2 {
 3 int k = 0;
 4 for (int i = 0; i < n; i++)
 5 {
 6 for (int j = 0; j < n; j++)
 7 {
 8 k++;
 9 }
10 }
11 
12 return k;
13 }

则其时间复杂度应为O(N²)

法则三----顺序语句

将各个语句的运行时间求和即可，比如有以下代码：

1 public static int sum(int n)
 2 {
 3 int k = 0;
 4 
 5 for (int i = 0; i < n; i++)
 6 k++;
 7 for (int i = 0; i < n; i++)
 8 {
 9 for (int j = 0; j < n; j++)
10 {
11 k++;
12 }
13 }
14 
15 return k;
16 }

第一个for循环的时间复杂度为N，第二个嵌套for循环的时间复杂度为N²，综合起来看sum方法的时间复杂度为O(N²)

常见的时间复杂度与时间效率的关系有如下的经验规则：

O(1) < O(log₂N) < O(N) < O(N * log₂N) < O(N²) < O(N³) < O(N!)

至于每种时间复杂度对应哪种数据结构和算法，后面都会讲到，从上面的经验规则来看：前四个算法效率比较高，中间两个差强人意，最后一个比较差（只要n比较大，这个算法就动不了了）。