小可:
王老师您好,了解了什么是大数据,今天我来听听关于算法的内容。
Mr. 王:
你好,想要学懂大数据算法,算法的基础知识是一定要了解的,你必须要知道如何设计和分析算法,我们才能谈及如何在大数据集合上研究算法。
小可:
我经常会听到“算法”这个词,计算机专业的同学总会提到,那么到底什么是算法呢?
Mr. 王:
至今为止,算法都没有一个准确的定义。每个计算机科学家和工程师都在设计算法、使用算法、分析算法、实现算法,但对于算法的定义依然是众说纷纭,很多书籍都曾经给出自己的定义,与其说那是一个定义,不如说都是对算法的一种诠释。的确,算法是一个很模糊、抽象的概念。
Mr. 王:
在解释“算法”这个概念之前,我们首先来谈谈,一个计算机科学家是如何解决问题的。我先问问你,计算机是用来做什么的呢?小可:计算、办公、游戏、影音娱乐,还有上网。
Mr. 王:
不错,宽泛地谈起计算机的用途真是数不胜数。不过总结起来,其实计算机做的事情就一个——解决问题。
Mr. 王:
对,生活中有很多问题,其中有些问题人工解决起来很费时费力,于是我们发明了许多工具,在这个层面上,其实计算机也是一种工具,本质上它就是解决问题的一种工具。
小可:
嗯,其中有些问题人工解决起来确实很费劲。那么计算机科学家又是如何解决这些问题的呢?
Mr. 王:
首先,如果希望计算机能真正地解决一个实际问题,我们先要将现实世界中的事物转化为模型,这个模型可以被计算机理解和处理,它可以表示成数据和指令等。这个过程我们称之为建立模型。在此过程中,我们需要把一个实际问题抽象成计算机可以理解的语言,或者说计算机可以理解的问题,才可以用计算机求解。
Mr. 王:
其次,我们要知道这个问题是不是可计算的。计算机可以解决很多问题,也有很多问题解决不了。那么,由此诞生的,研究一个问题是不是计算机可计算的、可解的计算机科学分支叫作可计算理论
。
Mr. 王:
当然,比如著名的“停机问题”。在这方面做出卓越贡献的科学家是非常著名的阿兰 · 图灵。图灵曾经提出过很多对计算机科学产生深远影响的理论,直到现在,我们使用的电子计算机在模型上依然可以称之为“图灵机”。停机问题在很多资料中也称作“图灵停机问题”。图灵已经进行了证明,停机问题是不可计算的。
小可:
那是不是说,我的电脑内存太小、CPU 太慢,有些特别大型的问题在我这里就“计算不出来”,这就是一个不可计算的问题呢?
Mr. 王:
不,这是不对的,不可计算的问题并不是出于 CPU 速度和内存大小等资源的限制而无法在一定的时间内完成,而是具有这样的特点,就是不论给计算机多大的内存、给它多快的 CPU 都是无法求解的。如果你的电脑 CPU 太慢、内存太小,在一台内存更大、CPU 更快的机器上,还是能够求解的,它不是一个不可计算的问题。
不过这里有一个问题:某个问题虽然是可计算的,但是对于这个问题我们急着要的结果要算几年时间,那么这个问题恐怕也“相当于”解决不了,或者说交给计算机解决已经没有什么意义了。所以我们必须要知道的一件事情是,这个问题能不能用计算机在我们可以接受的时间或者空间界限内解决。研究某个问题被计算机解决的时空下界限的计算机科学分支称为计算复杂性理论。计算复杂性理论主要研究的是某个问题可以被计算机求解的时间和空间下界限。它研究给出的问题的时空下界限,是任何算法都无法突破的,研究比下界限更快的算法是没有意义的,当发现某一个算法已经足够快到可以和计算复杂性理论中得出的下界限是同一个级别时,我们就不必再去提升它的效率了。同时,研究这种时空下界限有另一方面的目的,就是可以用来评价我们现在设计出来的算法与这个问题可以被解决的极限时间空间界限还有多远的距离,很多时候我们设计出来的算法还不足以达到这个极限界限,但有了这个界限,可以给我们接下来的研究指明一个方向。
总结起来,可计算理论和计算复杂性理论都是一个研究“问题”的范畴。
研究过问题之后,我们要考虑的就是如何去解决问题。这也是计算机作为一种工具的重要属性。想要解决问题,就需要我们设计算法。
Mr.王:
这里我们还是举个生活化的例子吧。比如,我们现在想要煮一锅汤,这就是一个问题。根据生活经验,我们认为它是可解的(可计算分析),也是理论上可以在我们接受的时间范围内解决的(计算复杂性分析)。这时,需要我们设计一个解决它的方法或者说一系列步骤。
小可:
我想想,煮汤我们可以想到的步骤就是洗菜、切菜、烧水、煮汤、出锅。哈哈。
煮汤的“算法”
Mr. 王:
很好,你已经在设计一个算法了。小可吃惊地说:啊?!这就是一个算法了? Mr. 王:从广义上讲,这种解决一个问题的一系列准确完整的步骤,就是算法。
小可:
哦,原来这已经是一个算法了?等等,王老师,我觉得我设计的这个步骤有些缺陷,如果按照这个步骤,在烧水的过程中,人一直是闲着的。如果先把水烧上,再去洗菜、切菜,是不是能更快地把汤煮完呢?也就是说,一个更好的步骤是,烧水、洗菜、切菜、煮汤、出锅。
煮汤的“算法”改进版
Mr. 王:
不错嘛,你刚刚很好地分析了你设计的算法。你注意到了一个算法具有的缺陷,并且分析它、改进它提出了更好的新算法。但是计算机科学中的算法分析要比这个略复杂些,一会儿我会给你讲解,为了理解大数据算法,必须要了解如何分析算法。