vlambda博客
学习文章列表

计算机对于很多人来说可能只是一个简简单单的生活工具，由于中国式的教育，我们从小就被灌输学习的观念，在很多家长的观念中除学习以外的东西是我们不应该接触的，所以我们大部分人没有什么很多的机会接触到计算机这一领域。在我们在常人的认知中，对于计算机的理解仅仅停留在表面上，绝大数的人就将计算机理解成我们平时所说的电脑，而人们对于电脑也仅仅认为是一个用于打游戏，听音乐，以及与人聊天的娱乐工具，至少我在大学之前还未接触这一领域时是这样认为的，电脑对与我来说仅仅是一个娱乐工具罢了，完全没有其他的用处，拿着电脑大部分时候就是打游戏。在高考后填志愿那个阶段我思考过很多的专业，最后选定了一个好找工作，薪资高以及和我的兴趣打游戏有关的计算机专业，但在大学学了一段时间后，我开始慢慢的了解计算机，以及它的历史，真正使用方法，以及它以后的发展，我的观念发生了很大的转变。在我目前的观念中，计算机是一个能改变人类时代的东西 ，就像有一句话所说“技术日新月异，人类生活方式正在快速转变，这一切给人类历史带来了一系列不可思议的奇点。我们曾经熟悉的一切，都开始变得陌生。”（约翰·冯·诺依曼(John vonNeumann),1958）它在当今的作用已经在慢慢体现出来，比如说人脸识别，指纹识别，无人驾驶，这一切看上去新奇的东西都与计算机有着不可分割的联系，可以说没有计算机就没有现在任何的智能设备，这句话一点都不夸张，对于如今任何一个享受着计算机所带来的便捷的人，有着一个都需要感谢的人——艾伦·麦席森·图灵（英语：Alan Mathison Turing，1912年6月23日—1954年6月7日），英国数学家、逻辑学家，被称为计算机科学之父，人工智能之父。是因为他的存在才有了计算机的出现，可能说这样不太合理，毕竟也许以后也会有像他一样的人出现，但，但他对于计算机领域的贡献可能是无人可及的，但是他英年早逝，实在是人类史上的一大惋惜，甚至有人说他的逝世让人类晚进步了几十年。

     言归正传，回到与这本书有关的东西，学过计算机的人都知道，计算机实际上是很笨的，它不会像人类一样变通，它非常的死板，只会执行你所输入的命令，它不自己创新，不会自己执行过多的动作，你给的命令是什么，它就怎么做，看上去非常听话，但这也导致了很多的问题，一旦遇到难一点的问题，就只能靠人类先给出相应的解决办法，然后将这些办法转化为计算机懂得计算机语言（就是代码），输入进计算机，然后计算机才能进行该问题的解答，这就牵涉到算法，而将这些语句输入计算机储存起来就牵涉到数据结构，我选择的这本书叫做数据结构与算法分析，作者马克·艾伦·维斯，现任美国佛罗里达国际大学计算机与信息科学学院教授，可能有人对数据结构与算法分析还不了解，这里来简单的解释下，数据结构主要研究组织大量数据的方法，而算法分析则是对算法运行时间的评估。随着科技的不断发展，计算机的速度越来越快，对于能够处理大量输入数据的程序需求变得日益急切。可是，由于在输入量很大的时候程序的低效率现象变得非常明显，因此这又要求对效率问题给予更仔细的关注。通过在实际编程前对算法进行分析，我们可以决定一个特定的解法是否可行，在这本书中我们能读到一些特定的问题并看到精心的实现方法是如何吧处理大量数据的时间限制从16年减至不到一秒的。因此若无法运行时间的阐释，就不会有算法和数据结构的提出。一旦将算法确定，还必须编写程序随着计算机的日益强大，它们必须解决的问题也变得更加巨大和复杂，这就要求开发更加复杂的程序。此书能够教授我们良好的程序设计技巧和提高我们的算法分析能力，使我们能开发出具有最高效率的程序

     这本书主要分为12个章节，分别是引论，算法分析，表栈和序列，树，散列，优先队列，排列，不相交集ADT，图论算法，算法设计技巧，摊还分析以及高级数据结构及其实现，我从中选择了几个自己感兴趣的章节作出自己详细的看法以及收获，

     让我先来说说排序这章，排序或许在实际的人工计算中看起来很简单，但对与计算机来说却是一大难题，对与计算机排序，你可能无法一次性的将一堆数字按照一定的顺序排列，计算机能做的就是一个一个的比较然后，再通过一系列变化，输出你想要的结果，一个一个比较听起来就知道很麻烦，而此书在本章要教的就是如何简化比较过程，相信大家都听过冒泡排序这个方法吧，这个是在计算机上比较原始的排序方法，简单的来说就是每次选定第一个数依次与后面的数进行比较，如果后面的数小于这个数就将两个数进行交换，如果后面的数大于这个数就将后面的数再依次与后面的数进行比较，最后得出一个最大的数，然后除去这个最大的数，再进行如上步骤，最后得到一个从小到大的排练顺序，这就是一个一个比较，非常麻烦，但也是比较有效的方法，而本章给我们讲述了一系列不同的算法，我选择一种叫做希尔排序的排序方法进行介绍，希尔排序（Shellsort）的名称起源于它的发明者希尔（Donald Shell）该算法是冲破二次时间屏障的第一批算法之一，不过，从它发明之日起，又过了若干年才证明了它的亚二次时间界（我也不是很理解）它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减少，直至只比较相邻元素的最后一趟序列为止。由于这个原因，希尔排序有时也叫做缩小增量排序，希尔排序所使用的序列叫做增量序列，只要第一项等于一的任何增量序列都是可行的，希尔序列对于我来说可能并不能很简化比较过程，但它带给我的是一种数学逻辑以及对一种思考方式，这比直接学会一种非常简化的排序更重要，这章还介绍了一些其他的排列方式，比如说堆排序，桶式排序，外部排序等等，我就不一一详写

接下来我想写一下这本书的算法设计技巧这章，如今我们已经涉及一些算法的有效实现，我们知道，当一个算法给定时，实际的数据结构无须指定，为使运行时间尽可能减少，需要编程人员来选择适当的数据结构，而这章把注意力从算法的实现到算法的设计的转变，我已经看到的大部分算法都是直接简单的，在这一章，集中讨论用于求解问题的五种通常类型的算法，对于许多的问题，很可能这些方法中至少有一种是可以解决问题的，这我要重点介绍一下贪婪算法，贪婪算法分阶段地工作。在每一个阶段，可以认为所作出的决定是好的，而不用考虑这种决定将来可能带来的后果。一般来说，这意味着选择的是某个局部最优的。这种“眼下能够拿到的就拿”的策略即是这类算法名称的来源，这样在我看来能充分得到目前最想要的，至少在目前是很好的。当算法终止时，我们希望局部最优就是全局最优。如果是这样的话，那么算法就是正确的，否则算法得到的是一个次优解（suboptimal solution）顾名思义就是比最优解差的解，这是我们所不想看到的。如果不要求绝对的最佳答案，那么有时会简单的用贪婪算法来生成得到一个近似答案，而不是使用一般产生准确答案所需要的复杂算法，这在一定程度上是非常方便的，至于贪婪算法最明显的例子就是找零钱问题。为了使用美国货币找零钱，我们重复地配发最大额货币。于是，为了找出十七美元六十一美分的零钱，我们拿出一张十美元钞，一张五美元钞，两张一美元钞，两个二十五美分硬币，一个十美分硬币，以及一个一美分硬币。这么做可以保证使用最少的钞票和硬币。这个算法不是对于所有货币系统都可行，但是我们可以证明它对美国货币系统是正确的。事实上，即使允许使用两美元钞和五十美分币，该算法也可行。这个例子可以直观的看出贪婪算法的再不同阶段下的不同作用

最后，总结一下吧，因为这本书所教的东西有很大部分超出了我现所学的，甚至接下来很长一段时间也无法接触，可能要到读研，读博才能用上和理解，所以我只看了一些我现如今可以理解的，但这本书提供的思维以及理解对以后的计算机学习非常有用。

2020.12