什么是算法?

1. 什么是算法

说实话,这个问题确实比较难以回答,我们先来看下百度百科对算法的定义:

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制

简单点说算法就是解决一个问题的步骤或者方法。比如针对去上班这个问题,我们的步骤是这样:

首先是出门走路到地铁站,然后坐地铁到里公司最近的地铁口下,最后走路到公司。这样一个过程,可以称之为完成这个上班任务的一个算法。但是很明显,去上班的算法有很多种,并不止坐地铁这一种,我们可以打的去公司、坐公交去公司等等,这样不同的步骤也对应着不同的算法。这些方式有好又有坏,有快也有慢,同样算法也是一样有好有坏有快有慢的。同一个问题,有多种解决方法,也就是多种算法,不同的算法之间也会好坏之分。

但是不管算法如何定义,它一定要具备以下五个特征才能称之为算法:

  • 有穷性:算法必须能在有限步骤之后终止。无穷无尽执行下去,那根本不是解决问题的办法,也就不能称之为解决该问题的方法;
  • 确切性:算法的每一步必须要有确定的含义;
  • 输入项:算法需要有输入或者说初始条件。比如我们上班的算法,我们的初始条件就是从家出发;
  • 输出项:算法必须要有一个或者多个输出。比如我们上班的算法,输出项就是顺利到达公司;
  • 可行性:算法必须是可以实现的步骤。那种天马行空、无法实现的方法就不能称之为算法了。如果坐着宇宙飞碟去上班,这显然不切实际,当然也就不能成为之上班的一个算法了。

2. 为什么要学习算法

有人问在大部分的工作场景下我们都用不到算法,那么我们为什么还要学习算法呢?首先,需要明确以下几个问题:

  • 工作中用不到并不代表工作中没有用到;
  • 工作中不常用并不代表面试不常考;

学 Java 的同学几乎天天都在用 HashMap 吧?但是大家有思考过存储在 HashMap 中 key 和 value 值是究竟用什么数据结构存储的?当使用 get() 方法查找 value 时用的什么算法?

但是我们一般是不会考虑这种问题的,因为这些工作都由编程语言给我们已经封装好了,我们只需要调用,调用,再调用!

那么对于 Python 也是一样的,我们用的 dict 等类型,它背后都是 Python 解释器给我们做了大量工作,实现了各种各样复杂的算法,给我们的使用带来了极大的方便,也导致我们大部分程序员似乎在工作中几乎看不到算法的应用

但是,不要忘了,我们是要追求进步的,如果你只是满足于调用各种 API 和方法来完成工作的话这个教程对你的意义不大。不过总会有现有的方法满足不了的业务场景,到那时候你该怎么办呢

此外,算法同样是大厂最喜欢拿来考察候选人员能力的一个方式。社招中最喜欢考察算法编程能力公司的当属今日头条,许多国外的互联网公司如微软、Facebook 等甚至会让你直接手写代码。

除此以外,掌握一定的算法基础有以下几个好处:

  • 锻炼自己的思维和编程能力保持解决问题的能力,这在工作中也是非常重要的一项技能;
  • 在面试中存在一定竞争力:优秀的编程者往往都是被大厂争夺的对象;
  • 在学习一些编程语言源码或者操作系统源码时会有深刻体会;

3. 如何学习算法?

学习基础算法的方法也很简单,就是刷题刷题理解后再刷题。刷题网站最出名的当属 leetcode,接下来是国内知名的就是牛客网了。如果对自己要求高,可以考虑刷 ACM 编程题,比较有名的有 POJ、ZOJ。当你能独立刷完上面的题目时,你已经是一名非常厉害的算法高手了,不过刷题也会耗费大量的业余时间,要懂得适可而止,享受生活。

4. 算法的评价标准

一个算法优劣的评价标准主要有两个:时间复杂度空间复杂度

4.1 时间复杂度

程序的运行时间往往有多方面因素综合决定,即使是同一种算法,不同的输入对应的运行时间可能也不相同。为针对运行时间建立一种可行、可信的评估标准,我们往往考虑输入数据的规模,这是最关键的因素。

通常情况下,问题的规模越接近,相应的计算成本也会很接近;而随着问题的规模扩大,相应的执行时间也会加长。因此,随着输入规模的扩大,算法的执行时间将如何增长,缓慢增长?线性增长,还是指数级增长?我们可以将算法的执行时间和问题的规模相互映射,得到了一个关于输入规模的函数,这个就可以称为该算法的时间复杂度

4.2 空间复杂度

空间复杂度类似,我们将问题的规模和算法所需的存储空间一一映射,得到的函数称之为空间复杂度。就目前业界而言,由于存储本身的廉价性,算法工程师们大多将算法的优化集中在时间复杂度上,所以往往将时间复杂度当做衡量一个算法好坏的标准。当然时间复杂度低且空间复杂度也低的算法是最好的选择,但是往往二者不能得兼,很多问题也需要具体情况具体分析

5. 本教程学习基础

本教程只需要简单的 Python 基础即可,没有其他的任何要求。主要是能理解一些解决问题的方法,比如递归、动态规划,需要一些抽象的思考能力。

6. 小结

今天我们简单介绍了下算法的概念以及为什么要学习算法进行了介绍。最后讨论了下算法的一般评价标准,主要是通过时间复杂度和空间复杂度进行衡量。今天的算法介绍就到这里了,下一节就开始算法实战以及相应的编程训练了,祝大家学习愉快。