数据结构与算法——绪论_数据结构与算法发展史

前言：数据结构与算法是计算机科学与工程的基础，它们的相互关系和作用是程序的本质。凭借一句话获得图灵奖的Pascal之父Nicklaus Wirth把它们表示为 算法+数据结构=程序

1、算法与数据结构的重要性

①相关定义

算法（algorithm）,非形式地说，就是任何良定义的计算过程，该过程取某个值或值的集合并产生某个值或值的集合作为输出。
——《算法导论》

---

数据结构（data structure）,是一种存储和组织数据的方式，旨在便于访问和修改。
——《算法导论》

直白来讲：
算法，就是问题的解法。广义来讲，我们所写的程序，乃至每个函数都是算法。
数据结构就是数据在计算机存储、组织的方式，指数据的组织形式 |

②为什么要学习算法

假设计算机是无限快的并且计算机的存储空间是无穷大且免费的，我们还需要学算法吗？
问题是：计算机的处理速度不是无限快的，存储空间也是有限且不便宜的。
——》所以，如何明智地使用计算机的资源就是个问题？
——》
而，我们这里所说的算法便是用来解决这个问题，它能帮你合理利用计算机的硬件资源，对问题作出更优、更快的解答。

③数据结构和算法的关系

一个卓越算法的实现，往往离不开精心设计的数据结构
例如：

• binary search tree(二叉搜索树)和RB-tree（红黑树）就是为了解决查找问题而发展来的特殊数据结构。
• max-heap（或min-heap）就可以用来协助所谓的heap sort（堆排序）
• 最基础的链表(Lintnode)就可以很快解决数据的插入、删除问题

可以说，特定的数据结构是为了实现某种特定的算法，两者难以分割。

2、算法发展史

早在1946第一台计算机ENIAC被发明以前，人们对于算法就已经研究了很长的时间。而算法历史上的每一个“第一次”，都为计算机的发展带来了重大影响，“算法是程序之魂，程序是算法之衣”，这句话从算法的发展史中略窥一二。

1️⃣算法概念的第一次被提出
“算法”，中文名称最早出自公元前一世纪的《周髀算经》；英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。

2️⃣历史上的第一个算法：欧几里得算法
公元前330年，被人们称为“几何之父”的欧几里得出生。他的成就之一就是给出
【欧几里得算法（或称辗转相除法）】，为求解最大公约数提供了快捷方法，直到今天的计算机学科，欧几里得算法仍然是最经典的几大算法之一。

3️⃣：历史上的第一个算法程序
“数字女王”阿达·洛芙莱斯（Ada Lovelace），世界上第一位程序员，为其朋友制作的巴贝奇分析机编写了求解【伯努利方程（详见高等数学教材）】的程序。这是人类史上的第一个算法程序。

巴贝奇分析机
》阿达·洛芙莱斯（Ada Lovelace）

4️⃣：第一次解决【算法定义】的难题
进入20世纪，算法得到了进一步的巨大发展。这个世纪，英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。
构造图：

机器头有一组内部状态，还有一些固定的程序。每个时刻，机器头都要从纸带上读入一个方格信息，然后结合内部状态查找程序表，再根据程序输出信息到纸带方格上，并转换自己的内部状态进行移动。
虽然图灵机十分地简单，但它可以用来模拟任何算法。图灵机对人们使用纸笔进行数学计算的过程进行了抽象，实现了用机器代替人类进行数学计算。
【图灵的思想对算法的发展起到了重要的作用。】

5️⃣ 现代 相关前沿算法举例

1. AI领域:神经网络算法
   神经网络是一个具有相互连接的节点的计算系统，其节点的工作方式更像是人脑中的神经元。这些神经元在它们之间进行处理并传递信息。每个神经网络都是一系列的算法，这些算法试图通过一个模拟人类大脑运作的过程来识别一组数据中的潜在关系。
   
2. 信息安全领域：DES加密算法：
   

3、算法举例：并行算法Goolge的优势

每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱， Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。
》
在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。
》
那么Google是如何解决这些问题的？
》
首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法 运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公 司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。
》
那么Google是如何开发出既有效率又能容错的并行计算的呢？

Google最资深的计算机科学家Jeff Dean认识到，Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：MapReduce。 这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。 MapReduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后，它的容错性能异常出色，就算一个server farm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了MapReduce算法。借助该算法， Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。
——摘自《算法的力量》李开复 作

4、如何学习算法和数据结构

• 1、多应用。计算机学科是工具学科，工具学科最重要的一个特点是：越用越熟练。在平时写代码时，把数据结构、算法应用到自己的程序中，帮自己解决问题。不光是这一门课程，要学好计算机技术，就要多用、会用。最简单的方式就是刷题，力扣、牛客、CF……，永远不缺题目。
• 2、主动自学。搞计算机技术，最重要的一点之一就是自学。学校的数据结构与算法课程，没有动态规划、没有回溯算法……而学校没讲的很多东西，在面试要用，在以后工作要用。这意味着，自己必须要自学很多东西。**好在计算机学科在网上学习资源丰富，github上有不少数据结构与算法项目。遇到BUG不会做，可以去stackoverflow、CSDN……咨询。**当然，前提是：自己主动去学，去取。
• 3、理解不了就多作图、多看图。数据结构与算法课程，会比以前的编程语言课抽象一点。算法的具体过程、各大数据结构的相关特点，有时候只凭借简单的敲敲代码就理解透彻。多画图，看看数据结构长什么样，多推导算法的具体流程，像归并排序、二叉搜索树等等，代码上难以理解的东西，通过作图就可以轻松理解。 当然，觉得自己用笔画画不好的，也可以用作图软件，C++/Python还有专门的作图库（我暂时只会这两个）。

5、相关资源推荐

课程资源——
中国大学MOOC
北京大学张铭老师主讲的《数据结构和算法》

B站
数据结构与算法基础（青岛大学-王卓）

辅助网站：
VisuAlgo.net/en
传送门
可以把算法和数据结构直观表示为动画

力扣
传送门

学计算机不打ACM、不打蓝桥杯、不打种种编程竞赛，可以。但不刷题，不动手，不可以。而刷题平台中，力扣是最适合学习数据结构与算法的。 网上有很多人说，力扣很难——不用理会。力扣恰恰是最基础的，不要等到大三大四再刷力扣，那会很急。

---

编程导航
传送门

是鱼皮老师做的网站，大大方便了学习资源的查找，上面的资源让我爽了好久。