大数据与计算机算法初学感悟（每周学点大数据）
大数据与计算机算法初学感悟（每周学点大数据）正文：No.3期：算法设计与分析理论上期回顾&查看方式：在上一期中，详细的讲述了大数据的特点、应用和算法~本期将层层深入解读算法设计与分析理论，实现了理论与实际，生动与深度的完美结合~了解上期详细内容，请在【灯塔大数据】微信公众号自定义菜单栏中点击“文章精选”—“文章连载”，进行查看
转载声明
本文为灯塔大数据原创内容，欢迎个人转载至朋友圈，其他机构转载请在文章开头标注：
“转自：灯塔大数据；DTbigdata”
编者按：灯塔大数据将每周持续推出《从零开始学大数据算法》的连载，本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作，以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用，带我们在大数据技术的海洋里徜徉~每周五定期更新，欢迎来做客呦！
上期回顾&查看方式：
在上一期中，详细的讲述了大数据的特点、应用和算法~本期将层层深入解读算法设计与分析理论，实现了理论与实际，生动与深度的完美结合~
了解上期详细内容，请在【灯塔大数据】微信公众号自定义菜单栏中点击“文章精选”—“文章连载”，进行查看
No.3期：算法设计与分析理论
正文：
在计算机科学中，研究算法的设计和评价算法“好坏”的分支，称为算法设计与分析理论。它研究如何去设计解决问题的算法，同时给出一个对算法在计算机中执行的时间和空间效率，评价这个算法是不是足够快、占用的空间足够小。到目前为止，高速的 CPU 和高速大容量的寄存器、缓存和内存依然是很昂贵的计算资源。另外，CPU 的运算速度和内存容量相对目前的大数据来说依然是不够的。所以设计高效率的算法，一方面是为了节约时间；另一方面也是为了节省金钱。从另一个方面讲，如果计算机的速度非常快、内存非常大，而且程度可以逼近无穷的话，恐怕我们就不再需要对算法进行分析和改进了，只要结果正确就可以了。不过从目前的数据量、研究的问题以及计算机的运算存储能力来看，还是有很大差距的。
计算机科学解决问题的办法
小可：嗯，不仅仅是设计算法，看来分析算法也是非常有必要的，设计一个好的算法可以事半功倍。
Mr. 王：算法设计与分析这一部分也是计算机科学解决问题最重要的部分，是计算机科学的核心所在。在科学的发展史上，也正是因为算法的出现，才使得计算机科学得以独立成为一门学科。在计算机科学领域，算法有着举足轻重的地位。
小可：我明白了，计算复杂性理论研究的是问题能解决的时空下界限，研究的是“问题”，而算法分析研究的是某一个方法的时间界限，研究的是“算法”。
Mr. 王从抽屉里拿出一组卡片，打乱顺序放在桌上，说：完全正确。为了让你了解计算机中的算法，我们举个机器能够实际运行的算法例子。我在这里举一个比较简单的问题。
排序
比如现在有一组数字，我们希望将它们从小到大排序。这是算法设计中一类很基础也是很重要的问题，叫作“排序”。当我们要设计一个算法时，首先要分析它的输入输出。如果将算法视作一个机器的话，我们要将所需要处理的数据当作“原料”放进机器，然后经过机器处理将“成品”从机器中取出来。放进机器里的“原料”就是算法的输入，而取出来的“成品”就是输出。
在这个问题中输入输出应该是什么呢？
小可：输入是一组数字，输出是由这组数字构成的从小到大的序列。
Mr. 王：嗯。算法取一个或一组值作为输入，并产生一个或一组值作为输出，算法是一个定义良好的计算过程，或者说是一系列的计算步骤，它可以将输入数据转化为输出结果。这就是算法在计算机中的定义。
小可：原来这就是算法啊。
Mr. 王：没错。好了，咱们回到排序的问题上，你想到什么方法了吗？
小可：这应该有很多方法吧，我可以大概看一看，动一动就可以排出来了。
Mr. 王：排序的方法确有很多，但是这个“大概看一看”，计算机可做不到，这违背了算法的确定性，定义不明确，计算机如何执行呢？你去想一种每一步都可以确定执行的方法。
小可一边思索着，一边摆弄着桌子上的卡片：嗯，可以这样，第一次，我找出整个集合里面最小的数，放在第一位；第二次，我找出第二小的数，放在第二位。依此类推，直到所有的数都被放进序列中。
Mr. 王：假设计算机每次只能比较两个数的大小，那么应如何发现一组数里的最小值呢？小可想了想，看着桌子上的卡片：这的确是个问题……可以这样做，我们先假设第一个数就是最小值，然后用后面的数与之比较，一旦发现有比它小的数，那么这个数就可以作为新的假设最小值，直到扫描了整个序列。
Mr. 王：不错，这样算法的步骤就被有效地具体化了。我们每一轮都执行选取最小值这个工作，这样第 n 步将第 n 小的数放在了第 n 个位置上，当 n 等于集合的大小时，就成功排列了。
这种实现排序的算法叫作“选择排序”。我们用伪代码描述就是下面的程序：
Selection-Sort(A n) begin
i ← 1；
while i<n do
min_position ← Find the minimal from A[i] to A[n];
swap (A i min_position); i ← i 1； end while
end
小可：伪代码是什么？
Mr. 王：伪代码是用来描述算法的一种语言，不是真正的计算机程序，但算法被描述成伪代码后，程序员就可以很容易地翻译成任何一种计算机语言了，这一步骤叫作算法的实现。而在算法被计算机语言实现后，可以形成相应的软件系统。我们今后的讨论也将常常用到伪代码来描述算法。伪代码并没有唯一的标准，很多书籍上使用的伪代码都是不同的，有时甚至就是英语或者中文句子。但是多数伪代码都是非常容易读懂的，具有一点编程基础的人都能够将它们实现为真正的计算机程序。
Mr. 王：我们来读读这段伪代码，看看它具体是怎么做的。
在伪代码中，我们常用“←”来表示赋值，它相当于很多高级语言中的等号“=”，它的意思就是把右边的值赋给左边。
就像我们之前描述的那样，每一轮，我们处理的对象都是还没有被排序的部分，在伪代码
中体现的就是不断增加的 i。第一轮，从第 1 个到第 n 个；第二轮，从第 2 个到第 n 个。这是由在大多数高级语言中都有的 while 语句实现的。
在每一轮中，我们都进行两个操作。假设现在执行的是第 i 轮，第一个操作是从未排序的部分中选出一个最小值；第二个操作是将这个值与第 i 个位置进行交换，也就做到了第 i 轮将第 i 小的数放到第 i 个位置上。
如果希望具体一点的话，则可以将求最小值的方法也写成伪代码：
findMin(A start end) begin
i ← start
min_pos ← i
while i <= end do
if A[i] < A[min_pos] then
min_pos ← i end if end while
return min_pos
end
我们首先假设第一个值是最小值，然后扫描整个数组，一旦发现有比它还小的值，那么这个值就设为假设最小值。这里始终更新的不是最小值，而是最小值的所在位置，然后通过这个位置来访问最小值。如果访问最小值的函数希望返回最小值的话，那么只需要稍作修改即可，这个就留给你回去修改了。
需要注意的一点是，我这里使用的伪代码中的数组下标是从 1 开始的。而像 C 语言这样的很多高级语言都是从 0 开始的，不过相信聪明的你一定能够在实现它的时候注意到这个问题并
进行相应的调整。
swap 这个函数非常简单，相信有一点编程基础的人都可以实现。你一定没问题吧？小可：没问题，我觉得像这样写就可以了：
swap (A i j) begin
temp ← A[i]
A[i] ← A [j]
A[j] ← temp
end
Mr. 王：至此，我们就完成了一个非常简单的算法——选择排序的设计。
小可：哦，那么我设计的这个算法怎么样呢？
Mr. 王：其实，这并不是一个很好的算法，它的时间复杂度是 O(n2)，而计算复杂性理论已经成功地证明了，基于比较的排序方法，最低的时间复杂度是 O(nlogn)。
小可：听不懂了。
Mr. 王：嗯，下一部分课我们就来讲讲具体如何评价一个算法。不论是大数据算法还是经典算法，算法的分析都是非常重要的，评价一个算法有助于考虑是否在某个问题的求解、工程的实现、系统的设计上使用该算法，同时也非常有助于通过改进而派生出新的算法。
下期精彩预告：
深入了解了算法设计与分析理论，下一期，让我们一起进阶大数据算法分析~
更多精彩内容，敬请关注灯塔大数据微信公众号，每周五不见不散呦！
内容来源：灯塔大数据
【灯塔大数据】微信公众号介绍：中国电信北京研究院通过大数据技术创新，自主研发了业内领先的“灯塔”大数据行业应用创新平台，灯塔面向市场研究、广告营销、商业地理、金融征信、人力资源等诸多行业领域，提供零售研究、消费者研究、店铺选址、精准营销、泛义征信，背景调查等服务，助力企业在大数据时代扬帆远航。
微信公众号【灯塔大数据】关键字回复信息：
回复【23个理由】 即可下载《大数据让你兴奋的23个理由》电子书
回复【世界论坛】可以下载行业应用PPT全文
回复【500强】 下载世界500强名单及中国公司完整榜单
回复【思维导图】可以下载12种工具的获取方式
回复【践行者】 观看电信用软件定义来“去电信化”视频
回复【企业家】下载图书购买链接
回复【云计算产业趋势分析】 下载分析报告PPT
回复【高峰论坛】 根据编号下载高峰论坛PPT资料
回复【主论坛】 查看《中国电信灯塔大数据高峰论坛》视频回放
回复【技术论坛】 收看技术分论坛视频回放
回复【程序代码】 下载程序代码
回复【 灯塔 】 查看更多关键字回复下载
