浅谈计算机算法优劣

周哲 周翔

摘要：1965年哈特马尼斯（Juris Hartmanis）和斯坦恩斯提出了算法复杂度的概念，从此算法有一个正规的评价标准，随着计算机技术的fazhan1，计算机科学家、算法分析之父高德纳（Don Knuth）对算法的复杂度提出了量化的衡量的指标。全球科技行业以计算机科学家、算法分析之父高德纳（Don Knuth）的为准。笔者下述对计算机科学家、算法分析之父高德纳（Don Knuth）的复杂度概念进行解析。

关键词：计算机；算法；高效

一、高效的算法到底有几个部分呢？

高德纳的思想主要包括这三个部分：

1. 在比较算法的快慢时，需要考虑数据量特别特别大，大到近乎无穷大时的情况。为什么要比大数的情况，而不比小数的情况呢？因为计算机的发明就是为了处理大量数据的，而且数据越处理越多。比如我和同学们做砸了的那件事，就是没有考虑数据量会迅速剧增。

2. 决定算法快慢的因素虽然可能很多，但是所有的因素都可以被分为两类。第一类是不随数据量变化的因素，第二类是随着数量变化的。例如：有一种大小排序的算法，它的运算次数是10倍的N平方，其中N是要排序的数字的数量。前面的那个10倍是个常数，和N的大小显然没有关系，10个数排序是如此，一亿个数排序时也是如此。而后面的N平方自然和N有关系了。高德纳讲，我们在研究算法时，不必考虑前面那个不变的常数，它是10倍，还是1倍，或者是100倍，只需要看后面那个变化的因素即可。因为N这个数趋近于无穷大时，前面那个不变的常数的影响是微乎其微的，算法的速度主要由后面一个因素决定。比如，当N=10的时候，N平方就是100；N=100，N平方就是1萬；N=1万，N平方就是一亿……总之，N平方这个因子的变化非常快。更广泛地讲，任何随着N变化的因素，通常会造成量级的差异。

二、高效率的算法就要少做事情

，对于一大堆无序的数字，从中随机挑选一个，比如是53，这个被随机选上的数字被称为枢值（枢纽的枢），接下来，将所有要排序的数字分成两部分，第一部分是大于等于枢值53的，第二部分是小于枢值53的。在第一步完成后，一大堆无序的数字就变得稍微有序一点了。第二步，从上面得到的两堆数字，分别采用第一步的方法各自再找一个枢值。对于第一堆，由于所有的数字都比53大，至少也等于53，因此，第二次随机挑选的枢值肯定是一个大于53的数字，比如79；类似地，对于第二堆，由于所有的数字都小于53，因此第二次随机挑选的枢值肯定小于它，，

例如：4，接下来我们把俩对数字再平均分成两堆的数字序列，在这样的情况下我们现在有了四堆数字，这样我们就很快查找到你想要的4号，使用类似的方法，我们对全校20000名高中生中，让全部同学到一个足够装下全部人的教室中上课，从中选出俩名尖子生，如果使用冒泡排序，那我们需要每位学生与全部学生相比，而使用上述的办法，一堆变两堆，两堆变四堆，四堆变八堆等等，方法：把2万人放到10所学校中，每所学校只有两千人，从各个学校先各自挑出学习尖子，再彼此进行比较，这就有效得多了。这就是归并排序原理。

快速排序是通常情况下最好的算法，但是，在极端的情况下，它的复杂度是N平方，和冒泡排序一样糟糕。而归并排序，即使在最坏的情况下，也能保证N乘以log（N）的复杂度，当然工程师们会想一些方法防止这种糟糕情况的发生。

三、算法高效率的本质

老师统计同学们的期末考试成绩，发现把一个班上五十个人的成绩排序丝毫没有错误，并不容易。后来我们发现比较可靠的办法其实是下面两种笨办法：

高德纳的思想，分析一下上述算法的复杂度。第一种算法很容易估算，50个人中找出最大的要比较49次，第二大的要比较48次，以此类推，大约是1200多次，是50的平方的一半左右。第二种方法复杂度，我们把50的整数扩展到任何整数N，排雷复杂度都是N的平方。在计算算法复杂度时，我们不关心一点点的差别，例如：几倍在计算机的世界中就是很小的数字。因此计算机科学家的思维与我们的思维不同在与，高德纳干脆删除了前面的常数因子，只保留后面的变量，他用了微积分中的一个概念——大写的O的概念，所有同等复杂度的算法，都被认为它们在"大O的概念"下是相等的。比如，上述冒泡排序算法的复杂度是O（N平方），插入排序也是O（N平方），属于同一个量级。此外，早期的计算机科学家还想出了其他的排序算法，复杂度都和它们差不多，在一个量级。

就是对两个组的排序。显然我们不应该再用冒泡排序。聪明一点的人马上会想到，既然能分成两组，就能把每个小组再分为两组，即分成四组，重复上面的算法，分别排序再合并。这样就能省3/4的时间。再接下来，四组可以分为八组，能省7/8的时间，八组可以分为十六组，时间就不断省得越来越多。分到最后每个小组只剩下两个人的时候，其实就不用排序了，只要比较一次大小即可。这种方法其实可以理解为两个过程，先是自顶向下细分，再自底向上合并。那么这种算法的复杂度等于多少呢？它相当于N乘以log（N），log（N）就是N的对数函数，大家不必在意N乘以log（N）是什么东西，只要记住它和N平方不一样，而且这个复杂度比前面的N平方小很多就行了。

好的计算机算法总是在极大的提升计算机的效率，效率是成千上百倍的提升，而不是去省掉几倍的速度的算法，所以我们在计算机编程时，要对计算机算法的方法和规律要熟记并且运用，这样才可以写出高效的代码。

参考文献：

[1]许兴权.浅议基于计算机算法的新型教学模式[J].教师，2013（26）：103.

[2]刘运龙，谢忠明.计算机算法教学初探[J].教师，2010（15）：74.