初学者学算法|谈什么是算法和时间复杂度

作者:孙宇晨 来源:www.5idf.cn 2020-08-21   阅读:

刚开始接触程序语言学习时,我们常常会听到身边的资工朋友或是网络上的文章时常提到一个名词:算法。请教google 大神后,维基百科给我们的答案是:
数学电脑科学 / 算学之中,算法/算法/算则法(algorithm)为一个计算的具体步骤,常用于计算资料处理自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数
等等,先别吐血。你早该知道要了解一个硬科学的知识时,维基百科通常不会是你一开始最好的朋友。
现在,让我们用一个简单的关系式来表示算法是什么。

算法的简单定义

算法的简单定义式:输入+ 算法= 输出
算法用最直白的方式来说,就是我输入一个东西,想要得到另外一个东西,经过的过程就是所谓的算法。假设我们输入一个2 还有一个3,如果想要得到6,我们需要在中间加上一个算法「乘号X」,让2 x 3 = 6。
又例如,我今天输入一颗橘子,想要得到一杯橘子汁,中间可能经过果汁机,或是经过愤怒的手。只要最后可以顺利得到橘子汁,中间的过程就可以称为它的算法。 

复杂一点的算法

而实际上,算法可能复杂得多,就像假设我们今天不只要做一杯橘子汁,而是要煮一碗洋葱炖汤,我们输入洋葱、油、水、盐,想要得到洋葱炖汤,这碗炖汤的算法可能会类似于
1.锅中倒入一匙油
2.热油
3.把洋葱切末
4.洋葱炒至金黄色后加入一锅水
5.加一些盐熬煮10分钟
在日常生活中,像这样的算法可说是随处可见。而在文章一开始提到,我们再接触程序时常听到「算法」的这个词,通常是指把这些步骤具体写成程序,用来达成特定目的的过程。这些算法简单的可能像是把一堆数字排序,复杂的可能如大家每天用的Facebook所用不断更新的News feed算法
在认识了算法基本的定义后,接下来,就让我们进一步来认识评断一个算法好坏的工具:时间复杂度(Time Complexity)。

时间复杂度

要判断一个算法的好坏,最基本的两个指标是这个算法有多快以及他需要用到的记忆体有多少。因为时间与空间的概念大致上是互通的,我们就先来了解比较常见的时间复杂度。
时间复杂度是用来评断算法执行快慢的指标,而实务上(*注)我们通常用大O 符号(Big O notation)来记录时间复杂度的快慢。接下来,先让我们用一个简单的例子来认识什么是大O 符号吧!

看电影跟大O 符号的关系

假设你今天心血来潮,想要重看经典电影名著《铁达尼号》。你有两个方法:(1) 走到离你家最近的租片店,租片来回需要花25 分钟。(2) 从网络上下载档案,一部需要花20 分钟。两者花的时间差距不大,但你可能会先选择从网络下载。
现在,让我们重新假设。你今天心血来潮,不只想要看《铁达尼号》,也想要顺便复习《哈利波特》全集+《魔戒》三部曲。此时,去租片店拿到这一拖拉库的电影还是只需要花走路的时间25 分钟,但从网络下载,你却需要等电脑下载4 个小时,这时,你可能不会选择从网络下载。 

在上面的例子中,如果选择去租片店取得电影,所要取得的时间不受想要看的电影部数影响。也就是你的脑袋不管输入几个电影需求(Input),最后得到电影档案(Output)的时间都不会因此增加。这样的特性,用所谓大O符号表示这个租片算法,我们会把算法的时间复杂度(常以T(n)代表)记为O(1)。
而如果选择从网络上下载电影,很明显的你输入n个电影需求,拿到电影的时间就会随着n成倍数成长。此时,我们会用大O符号把T(n)记为O(n)。
看到这里,我们可以对时间复杂度有一个最基础的认知,也就是:
大O 符号是用来描述一个算法在输入n 个东西时,总执行时间与n 的关系。

常见的时间复杂度比较

在设计一个程序算法时,我们会大O 符号比较算法执行的效率好不好。而通常,我们会希望一个算法至少能比O(n²) 还要快,如果能到O(n)、O(1) 甚至是O(log n) 的话是最理想的情况。
从下面这张图我们可以看到,当时间复杂度为O(n²) 时,只要输入的个数增加一些,它所需要花的时间就会大幅度的增加。想像一下当n = 10,000 时,O(n²) 所需要花费的时间就会比O(n) 的时间多一万倍。因此,在处理大量的资料或复杂运算时,一个好的算法设计可以省下的时间是很可观的。
 

进阶篇:深入时间复杂度的实际情况

到目前为止,我们认识了何谓算法,以及评断算法设计好坏的工具:时间复杂度。
接下来的部分,属于比较进阶的练功,对刚接触的新手可能会觉得有点难度或没办法完全理解。小小的建议是,如果你看第一次没办法完全体会,可以留到对程序设计更熟悉后再回头复习。而当然,如果有任何问题也都欢迎讨论!
接下来,就让我们来看一下进阶篇吧!

步骤次数

细心的读者可能会好奇,为何上面比较图的纵轴项目是步骤数而不是执行时间呢?
首先,我们要先来小小定义一下在程序设计中的「步骤次数」是指什么。通常在程序码中,每个动作只要被执行一次,我们就会说他是一个步骤,而这些动作包含印出、赋值、阵列读取等等。
举例来说,在程序码中我们宣告:
x = 10
赋予变数x数值10的这个动作就是一个步骤。
再举另外一个例子:
x = 10
for i from 1 to x:
    print("你好!")
在for 后面的回圈中,输出”你好!”这个动作被执行从x = 1 到x = 10 总共10 次,因此这个for 回圈总共的步骤次数就是10。但也别忘了,第一行x = 10 也是一个步骤,所以上面的三行程序码总共的步骤次数= 11。

执行时间vs 步骤次数

现在,我们了解了步骤次数后,我们终于可以再进一步了解一个重要观念:
算法有多快不是以秒衡量,而是以步骤次数
上面看电影的例子为了方便厘清大O 符号跟输入n 的关系,我们用时间来举例,但实际上,我们要真正衡量算法时,是以步骤次数来看。
为何看算法有多快不是用执行时间要几秒呢?想像一下,美国NASA 超级电脑需要执行1 秒的程序,拿到我们家里电脑执行可能需要100 秒。而同样的程序,用C 语言写跟用Python 写也跑的不一样快。因为电脑效能和语言特性的都会造成影响,因此用执行时间来衡量算法的快慢显然不是个稳定的指标。
回过头来使用上面看电影的例子,假设取得电影的动作我们可以用一个「只要一个步骤」的函数get_movie( ) 替代,则「想看十部电影之走路方案」的程序码就是单纯的
//想看十部电影之走路方案:步骤次数= 1次
// n = 10get_movie( )
而「想看十部电影之下载方案」的程序码可以写成
//想看十部电影之下载方案:步骤次数= 10次
// n = 10for i from 1 to n:
      get_movie()
我们从上面两段程序码可以观察,所谓「步骤次数」通常会以一段程序码中回圈执行的次数决定(先不考虑递回状况,因为这部分太复杂)。假如今天是从1 迭代到n 的回圈,代表步骤次数n。同样的如果是一个n 回圈里面再包一个n 回圈,代表他的步骤次数就是n²。而如果整段程序码都没有用到回圈或递回,则步骤次数通常以1 表示。

实务上我们如何记录时间复杂度

好奇的读者可能会有疑问,那如果一个程序中有好几个回圈,有单纯的回圈也有双重回圈,这样的步骤次数换成大O 符号要怎么表示呢?让我们从下面的程序码来瞧瞧:
for i from 1 to n:
      get_movie()for i from 1 to n:
      for j from 1 to n:
           get_movie()for i from 1 to n:
      for j from 1 to n:
           get_movie()
第一段的回圈步骤次数是n,第二段的步骤次数是n²,第三段的步骤次数又重复了一次n²,所以直观地想,这一大段的程序码的步骤次数就是2n² + n。
但实务上,当我们要将步骤次数转换成以大O 符号纪录的时间复杂度时,有一个很重要的原则,也就是要「尽可能化简」。
数学上,在n 相当相当大的时候,我们在比较两个数的大小时可以只比较他们的最高次方。因此在记录时间复杂度时,我们同样地会只记录最高次方的那一项。
另外,为了方便记录,我们也会省略所有系数,让时间复杂度的记录可以符合「尽可能化简」的原则。也因此,上面有2n² + n 个步骤的程序,我们会把它的时间复杂度简单记成O(n²)。
此时,也许细心的读者会有疑问,为何2n² + n 个步骤的程序,我们会将它的时间复杂度记的跟两倍步骤数( 4n² + 2n )一样,都是O(n²) 呢?
这边,我们可以把大O 符号想像成一个区段类别,而不是一个非常非常精确的记录单位。因此所有落在最大系数n² 这个区段的步骤数,我们就会全部将它们归在O(n²) 啰!

结论

呼!终于结束看完了这篇文章,希望身为程序麻瓜的读者还保持清醒,而有学过程序的读者也能借这篇文章复习一下。
如果对算法与时间复杂度还意犹未尽,敬请锁定AppWorks School 的Medium,我们在接下来的文章中会透过六个不一样的时间复杂度,去认识在程序设计中一定要知道的六种经典算法哦!最后,留下这篇文章的小小笔记,让大家方便温故知新!

温故知新

1. 算法的简单定义:输入+算法= 输出
2. 时间复杂度:衡量算法执行好坏的工具
3. 大O 符号:用来描述算法在输入n 个东西时,总执行时间与n 的关系
4. 在n 非常大时,好的算法设计可以省下非常多时间
5. 算法的速度不是以秒计算,而是以步骤次数
6. 实务上,我们只会纪录最高次方的那一项,并忽略其所有的系数
 

分享给小伙伴们:
如果本文侵犯了您的权利, 请联系本网立即做出处理,谢谢。
当前位置:孙宇晨博客 > 技术 > 《初学者学算法|谈什么是算法和时间复杂度转载请注明出处。
相关文章
  • 什么是机器学习?定义,类型

    什么是机器学习?定义,类型

  • 世界上第一个5G技术是什么?什么是5G

    世界上第一个5G技术是什么?什么是5G

  • 聚合物电容,为什么越来越多被选用?

    聚合物电容,为什么越来越多被选用?

  • 为什么有时候我们在电路中串联220Ω电阻

    为什么有时候我们在电路中串联220Ω电阻