周哲 周翔

摘要：1965年哈特馬尼斯（Juris Hartmanis）和斯坦恩斯提出了算法復(fù)雜度的概念，從此算法有一個正規(guī)的評價標(biāo)準(zhǔn)，隨著計算機(jī)技術(shù)的fazhan1，計算機(jī)科學(xué)家、算法分析之父高德納（Don Knuth）對算法的復(fù)雜度提出了量化的衡量的指標(biāo)。全球科技行業(yè)以計算機(jī)科學(xué)家、算法分析之父高德納（Don Knuth）的為準(zhǔn)。筆者下述對計算機(jī)科學(xué)家、算法分析之父高德納（Don Knuth）的復(fù)雜度概念進(jìn)行解析。

關(guān)鍵詞：計算機(jī)；算法；高效

一、高效的算法到底有幾個部分呢？

高德納的思想主要包括這三個部分：

1. 在比較算法的快慢時，需要考慮數(shù)據(jù)量特別特別大，大到近乎無窮大時的情況。為什么要比大數(shù)的情況，而不比小數(shù)的情況呢？因為計算機(jī)的發(fā)明就是為了處理大量數(shù)據(jù)的，而且數(shù)據(jù)越處理越多。比如我和同學(xué)們做砸了的那件事，就是沒有考慮數(shù)據(jù)量會迅速劇增。

2. 決定算法快慢的因素雖然可能很多，但是所有的因素都可以被分為兩類。第一類是不隨數(shù)據(jù)量變化的因素，第二類是隨著數(shù)量變化的。例如：有一種大小排序的算法，它的運(yùn)算次數(shù)是10倍的N平方，其中N是要排序的數(shù)字的數(shù)量。前面的那個10倍是個常數(shù)，和N的大小顯然沒有關(guān)系，10個數(shù)排序是如此，一億個數(shù)排序時也是如此。而后面的N平方自然和N有關(guān)系了。高德納講，我們在研究算法時，不必考慮前面那個不變的常數(shù)，它是10倍，還是1倍，或者是100倍，只需要看后面那個變化的因素即可。因為N這個數(shù)趨近于無窮大時，前面那個不變的常數(shù)的影響是微乎其微的，算法的速度主要由后面一個因素決定。比如，當(dāng)N=10的時候，N平方就是100；N=100，N平方就是1萬；N=1萬，N平方就是一億……總之，N平方這個因子的變化非?？?。更廣泛地講，任何隨著N變化的因素，通常會造成量級的差異。

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

，對于一大堆無序的數(shù)字，從中隨機(jī)挑選一個，比如是53，這個被隨機(jī)選上的數(shù)字被稱為樞值（樞紐的樞），接下來，將所有要排序的數(shù)字分成兩部分，第一部分是大于等于樞值53的，第二部分是小于樞值53的。在第一步完成后，一大堆無序的數(shù)字就變得稍微有序一點了。第二步，從上面得到的兩堆數(shù)字，分別采用第一步的方法各自再找一個樞值。對于第一堆，由于所有的數(shù)字都比53大，至少也等于53，因此，第二次隨機(jī)挑選的樞值肯定是一個大于53的數(shù)字，比如79；類似地，對于第二堆，由于所有的數(shù)字都小于53，因此第二次隨機(jī)挑選的樞值肯定小于它，，

例如：4，接下來我們把倆對數(shù)字再平均分成兩堆的數(shù)字序列，在這樣的情況下我們現(xiàn)在有了四堆數(shù)字，這樣我們就很快查找到你想要的4號，使用類似的方法，我們對全校20000名高中生中，讓全部同學(xué)到一個足夠裝下全部人的教室中上課，從中選出倆名尖子生，如果使用冒泡排序，那我們需要每位學(xué)生與全部學(xué)生相比，而使用上述的辦法，一堆變兩堆，兩堆變四堆，四堆變八堆等等，方法：把2萬人放到10所學(xué)校中，每所學(xué)校只有兩千人，從各個學(xué)校先各自挑出學(xué)習(xí)尖子，再彼此進(jìn)行比較，這就有效得多了。這就是歸并排序原理。

快速排序是通常情況下最好的算法，但是，在極端的情況下，它的復(fù)雜度是N平方，和冒泡排序一樣糟糕。而歸并排序，即使在最壞的情況下，也能保證N乘以log（N）的復(fù)雜度，當(dāng)然工程師們會想一些方法防止這種糟糕情況的發(fā)生。

三、算法高效率的本質(zhì)

老師統(tǒng)計同學(xué)們的期末考試成績，發(fā)現(xiàn)把一個班上五十個人的成績排序絲毫沒有錯誤，并不容易。后來我們發(fā)現(xiàn)比較可靠的辦法其實是下面兩種笨辦法：

高德納的思想，分析一下上述算法的復(fù)雜度。第一種算法很容易估算，50個人中找出最大的要比較49次，第二大的要比較48次，以此類推，大約是1200多次，是50的平方的一半左右。第二種方法復(fù)雜度，我們把50的整數(shù)擴(kuò)展到任何整數(shù)N，排雷復(fù)雜度都是N的平方。在計算算法復(fù)雜度時，我們不關(guān)心一點點的差別，例如：幾倍在計算機(jī)的世界中就是很小的數(shù)字。因此計算機(jī)科學(xué)家的思維與我們的思維不同在與，高德納干脆刪除了前面的常數(shù)因子，只保留后面的變量，他用了微積分中的一個概念——大寫的O的概念，所有同等復(fù)雜度的算法，都被認(rèn)為它們在"大O的概念"下是相等的。比如，上述冒泡排序算法的復(fù)雜度是O（N平方），插入排序也是O（N平方），屬于同一個量級。此外，早期的計算機(jī)科學(xué)家還想出了其他的排序算法，復(fù)雜度都和它們差不多，在一個量級。

就是對兩個組的排序。顯然我們不應(yīng)該再用冒泡排序。聰明一點的人馬上會想到，既然能分成兩組，就能把每個小組再分為兩組，即分成四組，重復(fù)上面的算法，分別排序再合并。這樣就能省3/4的時間。再接下來，四組可以分為八組，能省7/8的時間，八組可以分為十六組，時間就不斷省得越來越多。分到最后每個小組只剩下兩個人的時候，其實就不用排序了，只要比較一次大小即可。這種方法其實可以理解為兩個過程，先是自頂向下細(xì)分，再自底向上合并。那么這種算法的復(fù)雜度等于多少呢？它相當(dāng)于N乘以log（N），log（N）就是N的對數(shù)函數(shù)，大家不必在意N乘以log（N）是什么東西，只要記住它和N平方不一樣，而且這個復(fù)雜度比前面的N平方小很多就行了。

好的計算機(jī)算法總是在極大的提升計算機(jī)的效率，效率是成千上百倍的提升，而不是去省掉幾倍的速度的算法，所以我們在計算機(jī)編程時，要對計算機(jī)算法的方法和規(guī)律要熟記并且運(yùn)用，這樣才可以寫出高效的代碼。

參考文獻(xiàn)：

[1]許興權(quán).淺議基于計算機(jī)算法的新型教學(xué)模式[J].教師，2013（26）：103.

[2]劉運(yùn)龍，謝忠明.計算機(jī)算法教學(xué)初探[J].教師，2010（15）：74.