回顾
上一篇文章主要对书中的第一章节数据结构的绪论进行了总结和自己的一些理解，包括数据，数据元素，数据项还有数据对象，数据具有两个前提一个是可以输入到计算机内，第二个是能被计算机处理，然后数据元素就对应一张数据库表的一条记录，数据项就是数据库表的列，数据对象就是相同性质的数据元素的集合比如整张表就可以看做一个数据对象，那么在这种情况下，数据即可以是表中某一行某一列的内容，也可以是一个数据元素，更可以是一个数据对象。当然，有一点需要注意的是，虽然数据项是数据不可分割的最小单位，但我们实际情况下讨论数据的着眼点其实是数据元素。
接着，总结了一下数据结构的概念，数据结构是相对于数据元素来说的，就是一个数据对象之间，数据元素的相互关系和组织形式，分为逻辑结构和物理结构（存储结构）。逻辑结构是指数据对象中数据元素之间的相互关系，是面向问题的；物理结构是指数据元素之间的逻辑结构在计算机中的存储形式，是面向计算机的。“数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的”，“数据元素的存储关系并不能反映其逻辑关系”这两句话总结了逻辑结构和物理结构的关系，需要思考一下。然后，逻辑结构分为四种：集合结构，线性结构，树形结构，图形结构；物理结构分为两种：顺序存储结构，类似于排队，数组在内存中的存储结构就是顺序存储，链式存储结构，是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，那么怎么表示数据元素之间的逻辑结构呢，指针就应运而生了，指针：存放数据元素的地址，通过指针就可以找到数据元素在内存中的位置。
最后还稍微讲了一下数据类型（指一组性质相同的值的集合及定义在此集合上的一些操作的总称），抽象数据类型（我们对已有的数据类型进行抽象，就有了抽象数据类型。指一个数学模型及定义在该模型上的一组操作），以及抽象（指取出事物具有的普遍性的本质）的概念。
好了，接下来就是书中的第二章：算法。
算法
算法：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
怎么理解呢？很简单，比如我们做一道数学题，会有多种解决过程，那么每一种完整的解决过程就可以称为一个算法，那么指令就是解决过程中的每一步，每一步需要的东西可能又会由一个或多个操作得出。书中列举了一个最简单也是最经典的案例，高斯算法。高斯算法：将1到n的求和表示为（n+1）*n/2，相对于最基本的求和（1+2+3+..+n）简单了很多。这其实就是两个算法的比较，稍候会讲解。
那么算法和数据结构到底是什么关系呢？为什么说到数据结构就会说到算法？书中打了一个很经典的比方，如果一部话剧《梁山伯与祝英台》，最后变成了《梁山伯》会怎么样，当然还是可以演下去，但是演出质量就会下降好几个档次。那么数据结构和算法也是如此，如果单单讲数据结构也没有问题，但是可能讲完也不知道数据结构到底有什么用。这里怎么说呢，因为我也是小白，所以倒没有特别深的理解，所以这里就引用书中的介绍，可能当我学完整本书或者对数据结构和算法有更深的理解的时候，我会过来补充上我自己对于数据结构和算法两者之间的理解。=。=
算法具有五个基本特性：输入、输出、有穷性、确定性、可行性。
输入输出：算法具有零个或多个输入，至少具有一个或多个输出。算法可以没有输入（比如打印“hello world”，应该是所有计算机相关人员最熟悉的一句输出了），算法是一定需要输出的，输出的形式可以有多种，可以是打印输出，也可以返回一个或多个值等等。
有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。需要特别注意的是可接受的时间，这里有穷的概念并不是纯数字意义的，而是在实际应用中合理的，可以接受的“边界”，如果你一个算法跑20年才会出来一个正确的结果，虽然是有穷了，但是媳妇都熬成婆了，还有什么意义呢...
确定性：算法的每一个步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结构。算法的每个步骤被精确定义而无歧义。
可行性：算法的每一步都必须是可行的，也就是说，每一步都可以通过执行有限次数完成。可行性以为着算法可以转换为程序上机运行，并得到正确的结果。
那么对于同一个问题的多种算法，什么才是一个好的算法呢？接下来就来了解一下好的算法需要的特征。
正确性：一个好的算法最基本的要求就是正确性，正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。算法的正确性大致分为四个层次：1.算法程序没有语法错误；2.算法程序对于合法的输入数据能够产生满足要求的输出结果；3.算法程序对于非法的输入数据能够得出满足规格说明的结果；4.算法程序对于精心选择的、甚至刁难的测试数据都有满足要求的输出结果。因此算法的正确性大部分情况下都不可能通过程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，我们把层次3作为一个算法是否正确的标准。
可读性：算法设计的另一个目的是为了便于阅读、理解和交流。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难以调试和修改。我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，如果可读性不好，时间长了自己都不知道写了什么。所以可读性好坏是算法很重要的标志。
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
时间效率高和存储量低：时间效率值得是算法的执行时间，存储量指的是算法在执行过程中需要的最大存储空间。设计算法应尽量满足时间效率高和存储量低的要求。
那么如何度量一个算法的时间效率呢？也就是执行时间。俗话讲是骡子是马，拉出来溜溜。所以第一种方法就是事后统计方法。
事后统计方法：通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
但是这种度量方法实际上是很不科学的，理解一下，首先我们需要编制不同的算法，万一这种算法很糟糕，那不是浪费时间和精力吗？其次，时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣；再次，算法的测试数据设计困难，并且算法的优劣往往还与测试数据的规模有关。综上所述，事后统计方法，我们不予采纳。
基于此，我们很容易就想到，我们可以对算法在计算机编制前，先进行估算。也就是事前分析估算方法。
事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。
从事后统计方法的分析中，我们可以得出一个算法的执行时间，取决于算法本身的好坏，编译产生的代码质量（软件因素），机器执行指令的速度（硬件因素），以及输入的规模，那么抛弃软件因素和硬件因素，比较一个算法的好坏，就是比较在同等规模下，算法的执行时间效率。
那么，回到开篇提到的高斯算法和普通求和算法，将这两种算法写成计算机语言，如下：
普通求和：
int i, sum = 0, n =100; /* 执行了1次*/
for(int i = 1;i <= n;i++){ /* 执行了n+1次*/
sum = sum + i; /* 执行了n次*/
}
printf("%d",sum); /* 执行了1次*/
高斯算法：
int sum = 0,n = 100; /* 执行了1次*/
sum = (i+n)*n/2; /* 执行了1次*/
printf("%d",sum); /* 执行了1次*/
显然普通求和算法，执行了1+（n+1）+n+1 = （2n+3）次，而高斯算法，执行了1+1+1 = 3次。事实上，两条算法的开始变量定义，和结尾的输出语句是一样的，所以我们只关注中间的代码，我们把第一种方法的for循环看做一个整体，忽略头尾循环判断的开销，那么两个算法其实就是n次与1次的区别。算法差距显而易见，且随着n的增大，差距越来越明显。
这里需要理解的是，我们不关心编写程序所用的程序设计语言，也不关心程序将跑在什么计算机上，我们只关心它所实现的算法。这样，不计哪些循环索引的递增和循环的终止条件，变量声明和打印结果等操作，最终，在分析程序的运行时间时，最重要的是把程序看成是独立与程序设计语言的算法或一些列的步骤。
接下来，书中抛出了一个概念，函数的渐进增长。
函数的渐进增长：给定两个函数f(n)和g(n),如果存在一个整数N，使得对于所有的n>N，f(n)总是大于g(n),那么我们就说f(n)的增长渐进快于g(n);
那么渐进增长怎么理解呢？我们根据字面意思理解一下，我们都知道函数可以表示在一个坐标系中，当两个函数的两条线，慢慢靠近，直到某一点，之后，其中一条函数线一直都大于另一条函数线。
那么，我们判断一个算法好不好，我们可以对比几个算法的关键执行次数函数的渐进增长性，基本就可以分析出，某个算法，随着n的增大，它会越来越优于另一个算法，或者越来越差于另一个算法。其实这就是事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。
算法时间复杂度：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。
这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
那么如何分析一个算法的时间复杂度呢，也就是如何推导大O阶呢？如下：
推导大O阶：
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数函数中，只保留最高阶项；
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
得到的结果就是大O阶。
哈哈，是不是有点晕？下面我就来简单介绍一下书中的推导大O阶的例子，相信会很好理解。
常数阶：O(1)
再回想一下高斯算法的程序表示：
高斯算法：
int sum = 0,n = 100; /* 执行了1次*/
sum = (i+n)*n/2; /* 执行了1次*/
printf("%d",sum); /* 执行了1次*/
很明显，这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法，第一步就是把常数3改为1。然后发现，它根本没有最高阶项，所以这个算法的时间复杂度为O(1)，也就是常数阶。
线性阶：O(n)
for(int i = 0;i<n;i++){
/* 时间复杂度为O(1)的程序步骤序列*/
}
因为有n次循环，所以这个算法的时间复杂度就是O(n)，也就是线性阶。
对数阶：O(logn)
思考一下，下面这段代码的时间复杂度是多少？
int count = 1;
while (count<n){
count = count * 2;
/* 时间复杂度为O(1)的程序步骤序列*/
}
这段代码的意思就是有多少个2相乘后大于n就会结束循环，用函数来表达就是：2的x次方 = n，那么x=logn，所以这个循环的时间复杂度为O(logn)。
平方阶：O(n^2)
看下面代码：
int i , j;
for(i = 0; i < n ; i ++)
{
for(j = 0; j < n; j ++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
这是一个嵌套循环，其中内循环，刚才已经介绍了，就是O(n)，那么外循环，就是O(n)的时间复杂度再循环n次，那么整个的时间复杂度就是O(n*n)=O(n^2),也就是平方阶。
总结：对于循环来说，循环的时间复杂度，就是循环体的时间复杂度乘以该循环的次数。
变一下，下面的循环，时间复杂度又是多少呢？
int i,j;
for (i = 0;i<n;i++)
{
for(j = i;j<n;j++) //注意这里是j=i,不是j=0
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
分析一下这个嵌套循环，当i=0时，内循环执行了n次，当i = 1时，内循环执行了n-1次，...，一次类推，当i= n-1时，内循环执行了1次，所以总的执行次数是：
n+(n-1)+(n-2)+...+1 = n*(n+1)/2 = n^2/2+n/2;
根据大O阶推导，第一条没有加法常数，第二条，只保留最高阶项，所以保留n^2/2，第三条，去除这个项相乘的常数，也就是去除1/2，最终这端代码的时间复杂度为O(n^2)。
总结：我相信大家如果看下来都能够理解大O推导。其实理解大O推导不算难，难的是对数列的一些运算，更多的是考察数学知识和能力。（吓人~~）
那么常见的时间复杂度有哪些呢？
常数阶：O(1); 线性阶：O(n); 平方阶：O(n^2); 对数阶：O(logn);
nlogn阶：O(nlogn); 立方阶：O(n^3); 指数阶：O(2^n);
常见的时间复杂度所耗费的时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
我们有n个随机数字，打乱且不重复，要从中找到我们想要的数字，那么最好的情况就是第一个就是我们想要找的数字，那么这个时候的时间复杂度为O(1)，最坏的情况，可能那个数字就在这个队列的最后，这个时候的时间复杂度为O(n)。
最坏情况运行时间是一种保证，那就是运行时间不会更坏了。在应用中，这是一种最重要的需求，通常，除非特别情况，我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。
一般没有特殊说明的情况下，我们说的时间复杂度都是最坏时间复杂度。
第二章，终于整理完了，这篇整理的有点乱，有一些函数的渐进比较的图表，我没办法弄上来，所以可能中间会有点迷糊（我估计后面的内容也会有很多这种图表，所以我需要思考一下这些图表怎么拿上来）。但其实很明显的感觉出来，第二章算法，更多的是需要你的数学水平，需要进行一些推导和运算。然后对于我来说，虽然我高考数学还挺高的（130+），并且由于我的专业信息与计算科学专业也要学超级多数学（传说有这个专业的其他学校，这个专业都是数理学院的，我们学校是计算机学院，导致我们上大课经常跟数理学院的几个班一起上QAQ）；但是虽然如此，我真的觉得对不起我的历任数学老师，我真的忘记的一干二净，啊，难过，原地爆炸。。。在这里劝解一些，读书的朋友，如果想做计算机相关的，不管是考研还是工作，真的数学还是挺重要的，请以我为戒。
By the way，杭州最近的天气早上起床会有点小冷，希望大家注意身体，不要感冒。
Better Late Than Never!
努力是为了当机会来临时不会错失机会。
共勉！
网友评论