算法入门
1 从上学说起
转眼间秋天到了,天气转凉。愉快的玩了一个暑假的郭贴同学也要开学了!
这是郭贴第一次去新学校,他只知道学校的地址,而怎么去学校让他十分烦恼。
从郭贴家出发到学校有很多种方法,比如步行、骑车、或者打车等。另外即使是选择了步行上学,也可以有很多种不同的路线。
郭贴坐在沙发上挠起了头,不知道该选择哪种上学方式最好。
2 算法是什么
简单来说,郭贴如何选择上学方法 的这个问题的解决方案为「算法」,它的输入是郭贴的家和学校的地址,输出的是某种上学方法。
我们来看下百度百科给出的定义:
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
⚠️ 这一段相当于注解,不阅读不影响对整篇文章的理解,但强烈推荐。
请再读一遍上文的定义,读完接着往下看。
一般来说,定义是一个抽象的解释。它期望通过使用一个简单又具体的描述,帮助你理解新的知识。
实际上,对于不同的知识背景的人来说,这个解释并不一定是 简单 和 具体 的。
那这种形式化的定义又有什么作用呢?
我的认为是 限定范围,它限制了你理解这个知识的范围,在后续的学习中,不会理解的偏差过大。
那么请再读一遍定义,思考它的限制范围。
理解了算法的定义之后,我们来看算法的五个重要特性,分别为 「有穷性」、「确定性」、「可行性」、「输入」和「输出」。
输入和输出上文已经提到了,那另外三个概念代表什么呢?有穷性是指郭贴同学必须在移动了一定距离后到达学校,即一个算法必须是在执行了有穷步结束。确定性是指如果我们确定一个上学算法,只要给它的是相同的地址输入,就必定有相同的上学方法输出。可行性是指这个上学算法必须可行,即能在有限的资源下实现,比如提出一个坐火箭上学的方法就是不可行的。
好了,现在你也许大概知道了算法是什么,也许还没有弄清,不过不用太着急,带着你的思考继续往下看。
3 什么才是最好的
从上文的描述中可以想到,郭贴的上学算法有很多种。
在这些算法随便找出一个,似乎很容易,但对于郭贴来说,他发愁的是哪种方式上学最好?即 什么才是最好的上学算法?
要想回答这个问题,就必须先解决一个先导问题——我们用什么来评价一个算法的好坏呢?
举例来说,假如我们设定「交通速度」为指标,那么最快的肯定是汽车,但万一堵车了,反而成为最慢的交通方式。
对于算法的评价指标,这里我先抛出答案:
通常情况下,一个算法的好坏往往是通过评判「时间」和「空间」这两个纬度,对应着术语「时间复杂度」和「空间复杂度」。
为什么是「时间」和「空间」呢?这是一件很符合「直觉」的事情,你仔细想一下在生活中,时间和空间通常是我们最在意的东西。
同样在计算机里也是一样,最宝贵的资源就是运行时间和存储空间。
这里澄清一下,这个系列中所说的「算法」是大多数对应着我们常说的「数据结构与算法」中的算法,如有特殊情况我会额外注明。
下文中要介绍的算法,往往会在计算机上运行和调试,因此对「时间复杂度」和「空间复杂度」的分析就显得十分重要。
综上所述,如果我们分析所有算法的「时间复杂度」和「空间复杂度」这两个指标,然后找到表现最好的那个,也许就能找到我们想要的最好的算法!
4 怎么计算评价指标
时间复杂度这个词听起来很专业,其实就是计算算法运行的时间。
假设 CPU 每次运行时间固定,忽略读取数据等其他的时间,算法的运行的时间就等于算法的步数和单次运行时间的乘积。
我们如果能找到算法的步数,这个问题就基本解决了。
在一个算法中,有一些固定的处理数据的常量步数,也有一些随着输入规模变化的变量步数。
我们对时间复杂度的评估往往只想知道算法的大致规模,因此一般舍弃掉常量,取最大指数的变量。
举例说明:
$$ all_step = 3 + 5 + n + n^2 $$
3、5 是常量步数,n、n^2是变量步数,那么时间复杂度就是:n^2,记作O(n^2)
。
空间复杂度和时间复杂度类似,是计算算法需要的额外空间。它一般也只保留和输入规模正相关的最大指数的变量。
虽然这里我轻描淡写用一段就讲完了评价指标,但是具体中还有很多细节需要你自己实践中学习。
5 尾巴
郭贴通过分析算法的评价指标确定了一个最好的算法,第二天开开心心的去上学,并准时到达了学校!
上面的事情不知道有没有引发你的思考,生活、学习、工作等很多事情可能都是有最优算法的。
而大多数情况下,我们并没有思考当前的做法是不是最优算法,因此浪费了很多时间和精力。
这件事情的确值得我们深思。。。