hellow,everybody.今天我们来总结一下《大话数据结构》第二章----算法。那么首先，让我们一起回忆一下书籍目录关于第二章的内容吧。

算法

1.数据结构与算法的关系

2.两种算法的对比

3.算法的定义

4.算法的特性

5.算法设计的要求

6.算法效率的度量方法

7.函数的渐近增长

8.算法时间复杂度

9.常见的时间复杂度

10.最坏情况与平均情况

11.算法空间复杂度

以上就是算法的所涉及的十个概念，我们的总结也是按照以上是十个概念来进行的。那么我们one by one 来进行学习吧。

First,数据结构与算法的关系：

书中是用一个现实问题来解答二者之间的关系，假设你与你的girlfriend 一起去看爱情话剧《Romeo and Juliet(罗密欧与朱丽叶)。到了影院，发现海报上写的是《Romeo》,本以为是工作人员粗心大意写错了。后来才知道，原来美丽的Juliet不满自己报酬，所以就不愿意出席。没有Juliet,那么只能演Romeo的心理路程了。我是这么来理解算法与数据结构的关系的，好的算法是为了数据可以更高效的在计算机中存储。数据结构，算法可以单独拿出来讲，来学，来用。但是显然，意义不是很大。选择好的数据结构，来存储数据，选择好的算法来计算数据。目的都是为了让计算机可以高效运作。

Second,两种算法的比较：

高斯，是德国的著名数学家。说起来惭愧，关于等差数列，只知道有这么个东西，哇晓得它的历史。高斯上小学时，有一天班里同学不遵守纪律，惹得老师发怒。放学后，老师出了一道数学题，答出题目的同学才可以放学。题目是这样的:1+2+3+4+………100

同学们埋头在计算题目，不到一分钟，我们的天才数学家就把答案计算出来了，老师都感到不可思议（因为当时等差数列求和还没有诞生）。他的思路是这样的：

sum=1+2+3+4+………..+97+98+99+100

sum2=100+99+98+97+……+4+3+2+1

2*sum=sum+sum1(100个101)=10100

sum=sum+sum1/2=5050

等差数列求和的公式:（首项+末项）*项数/2

看一下，下面的两种算法。

int I;int sum=0;int n=100;

for(i=1;i<=n;i++)

{

      sum+=sum+I;

}

 

int i=1,;int sum=0;int n=100;

sum=(i+n)*n/2

 

大家体会到不同的算法的区别了么？所以，研究算法是很重要的。好算法浓缩都是智慧，都是知识。

Third,算法的定义:

何为算法？算法，解决问题，我们需要解决方案。具体的解决方案需要详细的步骤，方法。算法，就是这些步骤，方法的集合。对应到计算机中，就是一条条指令的集合。Note：一条指令可能包含多部操作。

Fourth,算法的特性:

算法具有她自己的一些特性，（1）有穷性：我们写出来的算法一定要保证是可以在一定时间内执行完的。（2）输出性：我们写出的算法一定要有输出，没有输出的话，那么这个算法也没有存在的意义。（3）输入性：大部分算法是需要输入参数的，个别的算法是不需要输入的，例外print：Hellow Word这句话。所以算法的输入可有可无。（4）可行性：写出的算法一定是要可以执行的。（5）确定性：写出的算法，一定能要明确的告诉计算机应该执行的操作。这就是算法的5个基本特性。

Fifth,算法设计的要求：

算法设计有几点要求：（1）正确性：我们设计出来的算法一定要是正确的。（2）可读性：我们设计出来的算法一定要让人可以看懂。（3）健壮性：我们设计出来的算法，生命力一定要旺盛，不能跑几个for循环就挂掉了。（4）时间效率高存储量低：时间效率，我们可以想想上面提到的两种算法比较。存储量，是指对计算机内存来讲的，要尽量少占用内存空间。

Sixth，算法效率的度量方法:

刚才我们谈到设计算法要求时，讲到了时间效率。算法效率，一般是指算法执行的时间。那么应该怎样去度量时间效率呢？书中讲了两种方法:1.事后统计法 2.事前分析估算法。关于事后统计法，是编写一个计时器，算法跑完，记录时间。算法的优劣，我们只能在算法跑完后才可以知道，显然这个方法是不科学。事前分析估算法，是常用的计算算法效率的方法。

拿我们刚才讲的两个算法为例:

 

从图中，我们可以看出这个算法一共执行了1+(n+1)+n+1次。

从图中，我们可以看出这个算法一共执行了1+1+1次。

因为这两个算法的不同之处仅仅在于循环体，与计算上。所以我们把相同部分去掉，再来看看执行次数。第一个我们称为A，A的执行次数为n次。第二个我们称为B，B的执行次数为1次。

其实A与B的差别在n次与1次。两种算法的优劣，可以很容易看出了吧？

我们再来个C算法：

从图中，我们可以看出，这个算法需要执行n的n次方。

我们来一起来对别一下3个算法的优劣:

如果我们的输入规模是10，那么算法A：需要执行10次  算法B：1次  算法C：10*10 100次。

随着输入规模的增大，算法C所花费的时间会越来越多。

当我们在分析估算算法的优劣时，一定要把算法的执行时间与输入的规模大小联系在一起，请看下图:

 

从图中，可以看出随着规模n的增加，对应的操作数量也会增加。这就好比，一个人的付出，是与得到成正比的。只要用心付出，踏踏实实的，就会得到别人得不到的东西。所以，平日的努力，一定要用心，不要做无用功。去努力，就要去用心。心不在焉，不如不干。

Seventh，函数的渐进增长

我们来判断一下两个算法，哪个优哪个劣。A算法，需要做2n+3次操作，B算法需要做3n+1次操作。单从字面上看不出优劣，我们可以进行一下分析：

当n<3时,B算法要优于A算法，当n>3时，A算法优于B算法。像这样的，输入规模n没有限制，当n>N时，函数总是大于另一个函数。这个函数是渐进增长的。

从图中我们可以看出，随着n的增大，表达式中的常数（+3、+1）影响很小，我们可以忽略。如上图的，A‘ B’。

我们在看一下算法C：

从图中我们可以看出，随着n的增加，表达式的结果不受常数的影响。与最高项数相乘的常数并不重要。如图C‘D’

Eighth，算法时间复杂度

我们用O（）来表示算法的时间复杂度，也称大O记法。

如何来推导大O记法呢?

常数阶：

我们来回顾一下上面提到过的例子，

这个算法的执行次数函数为f(n)=3，根据大O阶推导方法，我们来计算一下这个算法的时间复杂度

first:用常数1取代所有加法的常数，f(n)=1.

second:只保留最高阶项。没有最高阶项

third:如果最高阶项不是1，则去除与这个项相乘的常数。

最后得出f(n)=1.这个算法的时间复杂度为o(1).

如果我们把上面的算法改为这样：

再来计算一下算法的时间复杂度，根据公式推导，我们发现，时间复杂度还是f(n  )=1.这种与问题大小无关（n的大小 ），执行时间恒定的算法，

我称之为具有O(1)的时间复杂度。或者称为常数阶。

线性阶:

计算这个算法的时间复杂度，其实就是在计算循环体执行的次数。根据推导我们得出：时间复杂度为o( n ).

对数阶:

分析这个算法，我们发现。当X个2相乘大于n时所执行的次数，就是时间复杂度。2^x=n x=log2n.时间复杂度为O（logn )

平方阶:

看这个算法，最内层的执行次数函数为f(n )=n.外一次循环体只是执行n次内循环。所以这个算法的时间复杂度为o（n*n ).如果外层循环次数改为m，那么时间复杂度应为o(n*m )

Ninth,见的时间复杂度

上图就是常见的时间复杂度，最后三个不常用。我们不讨论，根据执行时间由小到大的顺序依次为:

O(1 )<O(logn )<O(nlogn )<O(n )<O(n*n )

Tenth,最坏情况与平均情况

平均情况是我们最理想的情况，我们谈时间复杂度，一般都是以最坏情况为标准。

Eleventh,算法空间复杂度

说实话，这章自己掌握的不好，好多都是摘录原文，没有经过自己的理解。不过，看懂一本书，最少也要看3遍。把这个留在第二遍，好了，这就是第二章的内容。来跟我一起学第三章吧！