算法：数据结构与算法的精髓

​算法（algorithm ）

是指令的集合，是为解决特定问题而规定的一系列操作。

它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。

一个算法通常来说具有以下五个特性：

• 输入：一个算法应以待解决的问题的信息作为输入。
• 输出：输入对应指令集处理后得到的信息。
• 可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。
• 有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的。
• 确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。

简单的说，算法就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是算法的逻辑形式，后者是算法的代码形式。

举例：如何求0+1+2+3+...10000=?

• 算法1：依次相加 while do-while for
• 算法2：高斯解法：首尾相加*50 (1+10000)*10000/2 100*101/2
• 算法3：使用递归实现：sum(100) = sum(99)+100 sum(99)= sum(98)+99 ..... sum(2) = sum(1)+2 sum(1) = 1

评价算法优劣的依据：复杂度（时间复杂度和空间复杂度）

算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间资源，因此复杂度分为时间和空间复杂度

时间复杂度是指执行算法所需要的计算工作量；

空间复杂度是指执行这个算法所需要的内存空间。

时间复杂度（Time Complexity)）定义

时间频度：

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。

但我们不可能也没有必要对每个算法都上机测试。

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度，表示为T（n），n表示问题的规模

时间复杂度：

但有时我们想知道它变化时呈现什么规律，想知道问题的规模，而不是具体的次数，此时引入时间复杂度。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，

若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

T(n)=O(f(n))

或者说：时间复杂度就是时间频度去掉低阶项和首项常数。

注意：时间频度与时间复杂度是不同的，时间频度不同但时间复杂度可能相同。

比如：某两个算法的时间频度是

T（n） = 100000n2+10n+6

T（n） = 10n2+10n+6 T(n) = n2

但是时间复杂度都是 T（n） = O（n2）

最坏时间复杂度和平均时间复杂度：

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例,该算法的运行时间不可能大于O(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。鉴于平均复杂度

第一，难计算

第二，有很多算法的平均情况和最差情况的复杂度是一样的。

所以一般讨论最坏时间复杂度

比如 我要求你在字典里查同一个字，告诉我这个字在字典的那一页。如果一页一页的翻，你需要多少时间呢？

最优的情况就是这个字在第一页，

最坏的情况就是这个字是 整本字典的最后一个字。

所以即使我故意为难你，你也不会花费比找整本字典最后一个字还长的时间。

当然，此时聪明的你就会想用部首、笔画等去查，才不要傻乎乎的一页一页翻，此时的你就会择优选择，因为此时你最坏的情况就是我给你部首笔画最多、除部首外笔画最多的一个超级复杂的一个字，但显然比翻整本字典快得多。

为了进一步说明算法的时间复杂度，我们定义 Ο、Ω、Θ符号。

Ο(欧米可荣)符号给出了算法时间复杂度的上界（最坏情况 <=），比如T（n） =O（n2）

Ω(欧米伽)符号给出了时间复杂度的下界（最好情况 >=），比如T（n） =Ω（n2）

而Θ(西塔)给出了算法时间复杂度的精确阶（最好和最坏是同一个阶 =），比如T（n） =Θ（n2）

时间复杂度计算：

根本没有必要计算时间频度，即使计算处理还要忽略常量、低次幂和最高次幂的系数，所以可以采用如下简单方法：

• 找出算法中的基本语句；

　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

• 计算基本语句的执行次数的数量级；
• 只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，
• 可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
• 用大Ο记号表示算法的时间性能。
• 将基本语句执行次数的数量级放入大Ο记号中。

时间复杂度举例：

• 一个简单语句的时间复杂度为O(1)。

int count=0;

• 100个简单语句的时间复杂度也为O(1)。（100是常数，不是趋向无穷大的n）

int count=0;

• 一个循环的时间复杂度为O(n)。

int n=8, count=0;for (int i=1; i<=n; i++)      count++;

T(n)=O(n)

• 时间复杂度为O(log2 n)的循环语句。

int n=8, count=0;for (int i=1; i<=n; i*=2)      count++;

1 2 4 8 16 32

230=1024*1024*1024 = 1000*1000*1000=10亿

• 时间复杂度为O(n2)的二重循环。

int n=8, count=0;for (int i=1; i<=100n; i++)       for (int j=1; j<=10n; j++)           count++;

• 时间复杂度为O(nlog2n)的二重循环。

int n=8, count=0;for (int i=1; i<=n; i*=2)      for (int j=1; j<=n; j++)            count++; 

• 时间复杂度为O(n2)的二重循环。

int n=8, count=0;for (int i=1; i<=n; i++)      for (int j=1; j<=i; j++)            count++;

1+2+3+4....+n=(1+n)*n/2

需要复杂些数学运算：1+2+3+.....+n=(n+1)*n/2 时间复杂度是 O(n2)

后面讲解查找和排序算法时会大量的设计时间复杂度，作为选择查找和排序算法的重要依据

常用的时间复杂度级别：

• 常数阶O(1)
• 对数阶O(log2n)
• 线性阶O(n)
• 线性对数阶O(n*log2n)
• 平方阶O(n2)
• 立方阶O(n3)
• ...
• k次方阶O(nk)
• 指数阶O(2n)
• 阶乘阶O(n!)

上面各种时间复杂度级别，执行效率越来越低。

大家发现对数阶O(log2n)和线性阶O(n)的效率差异了吗，当n=10的8次方（1亿）时，执行此时一个是1亿次，一个是8次。

所以编写算法时一定要注意时间复杂度的选择。

空间复杂度（Space Complexity)）：

算法的存储量包括:

• 程序本身所占空间
• 输入数据所占空间；
• 辅助变量所占空间

输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：

S(n) = O(g(n))

• 空间复杂度分析1：

int fun(int n){     int i，j，k，s;       s=0;      for (i=0;i<=n;i++)                      for (j=0;j<=i;j++)                     for (k=0;k<=j;k++)                           s++;       return(s);}

由于算法中临时变量的个数与问题规模n无关，所以空间复杂度均为S(n)=O(1)。

• 空间复杂度分析2：

void fun(int a[]，int n，int k) {     //数组a共有n个元素    int i;    if (k==n-1)         for (i=0;i<n;i++)　　           printf(“%d\n”，a[i]);  //执行n次    else {          for (i=k;i<n;i++)            a[i]=a[i]+i*i;　　//执行n-k次          fun(a，n，k+1);    }} 

此属于递归算法（后续讲解），每次调用本身都要分配空间，fun(a,n,0)的空间复杂度为O(n)。

注意：

• 空间复杂度相比时间复杂度分析要少
• 对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元；
• 若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。