程序 = 数据结构 + 算法

作者 谢恩铭 转载请注明出处
公众号「程序员联盟」(微信号:ProgrammerLeague )
原文:https://www.jianshu.com/p/b2f23799a5bb


《数据结构和算法》全系列

内容简介


  1. 前言
  2. 什么是算法
  3. 算法无处不在
  4. 计算机的“特权”角色
  5. 什么是数据结构
  6. 第二课预告

1. 前言


程序员应该知道:程序 = 数据结构 + 算法(Program = Data Structure + Algorithm )。

作为一个程序员,如果不了解数据结构和算法,应该会不太好意思出门跟人家打招呼。

在这个课程里,我会带大家以循序渐进、轻松幽默的形式入门数据结构和算法,相信我们会度过一段非常愉快的时光。

你会发现,入门数据结构和算法,其实一点都不难

话休絮烦,我们直接进入主题。

2. 什么是算法


首先我们来思考一个问题:

什么是算法?

要很准确地回答这个问题并不容易,但其实也没那么难,我不需要用一大堆理论来说清楚什么是算法,况且算法也不仅限于 IT 编程领域。

所以一个通俗易懂的回答可以是:

算法 是以简单概念的形式对如何解决问题的一种精确描述。

所以说:

  • 算法是一种描述(description),且是一种精确的描述
  • 描述什么?描述如何解决问题
  • 以什么样的形式来描述?以简单概念的形式

说到问题,在日常生活中,我们经常需要解决问题。有的人可能每天需要解决很多问题,有的人可能就是问题本身。

下面我就来描述一个生活中的问题,从广义上来考虑“问题”和“算法”的概念。

3. 无所不在的算法


我们可以用一个几乎关乎所有人的问题来开始说明:烹饪。毕竟“民以食为天”。

假设你饿了,你来到厨房,想整点什么吃的,正好你看到了一包方便面,然后你不自觉舔了舔舌头,你想吃方便面了(如果你正好是在睡觉前看到这里,请不要打我。不鼓励大家多吃方便面。这里的例子也可以是煮饭、煮面或者烹饪其他食物),那你应该怎么烹饪它呢?

这是一个简单的过程(这里只说最简单的水煮的方式,请大家不要纠结烹饪的细节,也许你有其他更好的烹饪方便面的方式):

  • 在锅子里倒入适量水

  • 在炉子上点起火来(如果是电磁炉就不用火)

  • 把锅子放在炉子上

  • 等待水开,转中火

  • 把方便面饼放入锅中

  • 煮半分钟

  • 放入所有调料包

  • 煮 1 分钟

  • 出锅

美味的方便面

可以看到,我已经以简单概念的形式精确描述了如何解决“煮方便面”这个问题。

所以上面这套流程的描述,你可以把它称为“算法”,这个算法是专门针对“煮方便面”这个问题的。

你会注意到上面的例子中有许多暗含的东西:我说你最初拥有一包方便面,但你也需要锅子、水,等。

我们可能会处于所有这些东西都不可用的特定情况下,然后我们就得使用另一种算法(或许先得自己造口锅出来)。

上面的流程里,我使用的各条指令(步骤)是比较“精确的”,但我们可以精简到更少的指令,或扩充到更多指令。你也许会说,如果要更精确地说,得说明如何把水装进锅子里。

如果要根据这个食谱来烹饪方便面的人不知道如何执行“在锅子里倒入适量水”这一指令,则有必要用更简单的术语解释(例如,需要解释如何使用水龙头)。

类似地,在我们编程时,你使用的算法的精度取决于许多参数:你使用的编程语言,可用的库,等等。

4. 计算机的“特权”角色


如果在日常生活中能找到算法的痕迹,为什么我们却主要在计算机科学(Computer Science)中讨论它呢?

原因很简单:
计算机(或电脑)非常擅长执行重复性任务。它们快速,高效,“任劳任怨”,从不喊累。

假设我们可以描述用于计算 3 的平方根的小数的算法(这算法得是人可以操作的)。利用这个算法,你可以使用纸和笔来计算 3 的平方根的前 7 个小数位(1.7320508)。

但如果需要你计算 3 的平方根的前 10 万个小数位呢?用纸和笔会算到怀疑人生。这种时候,计算机将变得更加合适。

我们可以设计出不少用于信息处理的算法。说到信息处理,通常有以下几类:

  • 研究
  • 比较
  • 分析
  • 分类
  • 提取

计算机通常在这些方面更加有优势,可以很好地处理大量信息。

你可能已经想到了著名搜索引擎谷歌(最初谷歌正是靠着其搜索算法的实力才能主导市场,成就了今天几千亿美元的市值),但这种活动并不仅限于互联网领域。

当你玩实时战略游戏的时候,如果你下达指令给一个单位,让它移动。此时电脑需要掌握很多的信息(例如地图的结构,单位的起点,单位的终点),它也必须产生新的信息:单位应走的路线。

所以其实算法源于生活(毕竟是人想出来的),但是我们通常在 IT(信息技术)这个领域才讨论算法,因为计算机的特殊性。

5. 什么是数据结构


上面说到了算法,现在我们来聊聊数据结构。

除了处理信息外,还必须考虑如何存储信息。存储信息的方式可能会对其处理方式产生非常重要的影响。

具体地说,以字典为例:

我们可以将字典定义为“单词及其定义的一个集合”(一个单词对应一个定义)。

如果一部字典里的单词是胡乱排序的,这样的字典应该很难使用吧。比如你要找一个单词的定义,你得一页页地翻字典,直到找到那个单词。

按字母顺序来排列单词显然是一种非常有效的解决方案,可以快速找到你所要的单词。

算法(描述方法)和数据结构(描述组织)之间存在非常紧密的联系。
简单来说,对信息的存储方式就是数据结构关心的事,对信息的处理方式就是算法关心的事。

通常,某些数据结构对于某些算法的实现至关重要;反之亦然。

例如,如果我们想要在已经按字母顺序排列好的字典中添加一个新单词,我们就不能只是将这个新单词写在字典的最后一页的空白处,而是必须使用算法将其添加到正确的位置。

因此,数据结构的研究与算法的研究是密不可分的,我们需要同时来学习它们。

6. 第二课预告


今天的课就到这里,一起加油吧!

下一课我们将用一个小故事来引出算法复杂度的学习(真正算法复杂度的讲论将在第三课):

敬请期待下一课:数据结构和算法 | 第二课:小鸭子们去度假


我是 谢恩铭,软件工程师,慕课网精英讲师 Oscar 老师,终生学习者。
热爱生活,喜欢游泳,略懂烹饪。
人生格言:「向着标杆直跑」