程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

作者 謝恩銘捆探，公眾號(hào)「程序員聯(lián)盟」（微信號(hào)：coderhub）然爆。
轉(zhuǎn)載請(qǐng)注明出處。
原文：http://www.reibang.com/p/060ef52580af

《數(shù)據(jù)結(jié)構(gòu)和算法》全系列

內(nèi)容簡介

1. 前言
2. 尋找最大和最小的元素
3. 尋找不重復(fù)的元素
4. 尋找不重復(fù)的元素：另一種方法
5. 第一部分第六課預(yù)告

1. 前言

經(jīng)過 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第三課：算法復(fù)雜度（上） 和 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第四課：算法復(fù)雜度（下） 黍图，我們講完了算法復(fù)雜度曾雕，是時(shí)候來做點(diǎn)實(shí)踐的練習(xí)，鞏固一下所學(xué)知識(shí)點(diǎn)了雌隅。

算法的復(fù)雜度是個(gè)不錯(cuò)的知識(shí)點(diǎn)翻默，但是它與我們這門算法的課程有什么關(guān)系呢？我們慢慢來看恰起。

算法學(xué)（Algorithmics）是設(shè)計(jì)和研究算法的科學(xué)修械，它的歷史可比計(jì)算機(jī)科學(xué)的歷史久遠(yuǎn)多了，但今天算法學(xué)卻幾乎全由計(jì)算機(jī)科學(xué)家實(shí)踐检盼。

算法學(xué)是一個(gè)非常廣泛的領(lǐng)域肯污，需要不少數(shù)學(xué)知識(shí)。當(dāng)然了吨枉，并非所有計(jì)算機(jī)科學(xué)家都需要成為天才的算法學(xué)家蹦渣。從算法的角度來看，大多數(shù)程序員面臨的問題實(shí)際上非常簡單貌亭。

但我們有時(shí)需要實(shí)現(xiàn)一些更復(fù)雜的東西柬唯。在這種情況下，算法方面的基本知識(shí)就會(huì)顯得非常有用圃庭。我們并不要求你發(fā)明一種革命性的新算法并給出其復(fù)雜度的具體證明锄奢，但為了能夠準(zhǔn)確地使用那些在網(wǎng)絡(luò)上或軟件庫中找到的算法，還是有必要接受一下“基礎(chǔ)培訓(xùn)”的剧腻。

懂算法會(huì)讓你更有效率拘央，能夠更好地理解你所要解決的問題，也不會(huì)寫出不規(guī)范的代碼：有一些代碼盡管可以正常運(yùn)行书在，但從算法的角度來看卻是不合理的灰伟。一個(gè)經(jīng)驗(yàn)不豐富的程序員可能會(huì)直接使用這些不合格的算法（他會(huì)想：“代碼能運(yùn)行，所以應(yīng)該沒什么問題”）儒旬，但你因?yàn)槎惴ɡ刚耍湍芎芸彀l(fā)現(xiàn)代碼的問題，并改寫出一個(gè)優(yōu)秀得多的版本栈源。

聽我說了這些挡爵，你可能有點(diǎn)躍躍欲試了。下面是兩個(gè)簡單的對(duì)于算法復(fù)雜度的研究題凉翻，它們可以讓你更準(zhǔn)確地了解算法復(fù)雜度的作用了讨。

2. 尋找最大和最小的元素

問題 1：
有一個(gè)正整數(shù)列表捻激，我們想要找到列表中最大的整數(shù)。

這個(gè)問題的經(jīng)典解法如下：遍歷此列表前计，并一直保存迄今為止發(fā)現(xiàn)的最大元素胞谭，稱其為“當(dāng)前最大值”。

我們可以將此算法描述為：

一開始男杈，“當(dāng)前最大值”等于 0丈屹。我們用列表中每一個(gè)元素去和“當(dāng)前最大值”做比較，如果當(dāng)前遍歷到的元素比“當(dāng)前最大值”更大伶棒，則將“當(dāng)前最大值”設(shè)為當(dāng)前元素的值旺垒。在遍歷完整個(gè)列表后，“當(dāng)前最大值”就真的“實(shí)至名歸”了肤无。

下面我們給出此算法的一種實(shí)現(xiàn)先蒋，是用“世界上最好的編程語言” PHP 來實(shí)現(xiàn)的（當(dāng)然，你也可以用其他編程語言來實(shí)現(xiàn)）：

<?php
function max($list) {
   $current_max = 0;
   foreach ($list as $item)
       if ($item > $current_max)
           $current_max = $item;
   return $current_max;
}
?>

我們可以快速驗(yàn)證此算法是正確的：我們只需要確認(rèn)在此算法執(zhí)行時(shí)宛渐，“當(dāng)前最大值”總是等于到目前為止所遍歷到的列表元素里最大的那個(gè)值竞漾。

我們也注意到此算法是會(huì)“結(jié)束”的，它不會(huì)陷入無限循環(huán)：此算法遍歷完整個(gè)列表窥翩，然后停止业岁。這看起來像一個(gè)不重要的細(xì)節(jié)，但實(shí)際上有一些編程語言里是可以表示無限多元素的列表的：在這種情況下寇蚊，我們的算法是不正確的笔时。

現(xiàn)在讓我們研究此算法的復(fù)雜度。我們要考慮哪些操作呢仗岸？顯然允耿，大部分工作都在于將當(dāng)前元素與“當(dāng)前最大值”進(jìn)行比較（畢竟，“當(dāng)前最大值” current_max 的初始化（初始化為 0）并不占多少運(yùn)行時(shí)間）爹梁，因此我們計(jì)算“比較操作”的次數(shù)右犹，將其作為此算法的操作數(shù)提澎。

算法的執(zhí)行時(shí)間取決于哪些參數(shù)呢姚垃？可以想見，執(zhí)行時(shí)間并不依賴于列表中每個(gè)元素的值（在此盼忌，我們假設(shè)兩個(gè)整數(shù)的比較時(shí)間是恒定的积糯，不論它們的值是多少）。因此谦纱，我們用元素列表的長度 N 來量化輸入看成。

對(duì)于一個(gè)包含 N 個(gè)元素的列表，我們要進(jìn)行 N 次比較：每個(gè)元素都與“當(dāng)前最大值”進(jìn)行一次比較跨嘉。因此川慌，算法的時(shí)間復(fù)雜度是 O(N)：它的執(zhí)行時(shí)間是呈線性的，與列表的元素?cái)?shù)目 N 成正比。

那么梦重，此算法的空間復(fù)雜度是多少呢兑燥？此算法使用了一個(gè)列表，里面的元素占用了一定的內(nèi)存空間琴拧。但是降瞳，這個(gè)列表在我們查找其最大元素之前就已經(jīng)存在了，它所占用的內(nèi)存空間并不是由我們的算法分配的蚓胸，因此我們說此列表的元素?cái)?shù)目 N 并不會(huì)被考慮到算法的空間復(fù)雜度的計(jì)算中挣饥，我們只考慮由我們的算法直接申請(qǐng)的內(nèi)存。

而我們的算法直接申請(qǐng)的內(nèi)存空間幾乎可以忽略不計(jì)沛膳，因?yàn)樽疃嗑褪钦加昧艘粋€(gè)臨時(shí)變量（current_max）扔枫，用以存儲(chǔ)“當(dāng)前最大值”。因此锹安，我們的算法所占用的內(nèi)存空間不依賴于列表的長度： （我們將空間復(fù)雜度記為 O(1)茧吊，表示它不依賴于 N）。

對(duì)于我們的算法八毯，現(xiàn)在只剩下一個(gè)小細(xì)節(jié)要注意了：如果我們的列表是空的搓侄，那么返回的最大值將是 0。要說“一個(gè)空的列表的最大值是 0” 顯然不一定是正確的：在某些情況下话速，如果列表是空的讶踪，最好返回一個(gè)錯(cuò)誤。

因此我們可以改進(jìn)一下我們的算法：我們不再為“當(dāng)前最大值”賦初值為 0泊交，而是以列表的第一個(gè)元素（如果該列表為空乳讥，則返回一個(gè)錯(cuò)誤）作為“當(dāng)前最大值”的初始值。然后廓俭，我們從第二個(gè)元素開始比較云石。

經(jīng)過改進(jìn)后的算法執(zhí)行 N-1 次比較（因?yàn)槲覀儾槐貙⒌谝粋€(gè)元素與它自己進(jìn)行比較）。不過研乒，這并沒有改變算法的時(shí)間復(fù)雜度：N 和 N-1 之間的時(shí)間差并不依賴于 N汹忠，它是恒定的，因此我們可以忽略它：兩種算法具有相同的時(shí)間復(fù)雜度雹熬，它們都是時(shí)間線性的（時(shí)間復(fù)雜度是 O(N) ）宽菜。

最后，我們注意到第二個(gè)算法也適用于負(fù)數(shù)（如果列表的所有元素都是負(fù)數(shù)竿报，第一個(gè)算法會(huì)返回 0铅乡，這顯然不正確）。因此改良后的第二個(gè)算法更通用烈菌，也更好阵幸。

當(dāng)然了花履，查找列表中最小值的算法和查找最大值是類似的，我們就不贅述了挚赊。

3. 尋找不重復(fù)的元素

現(xiàn)在我們來看第 2 個(gè)問題臭挽。

問題 2：
有一個(gè)列表 1，其中包含重復(fù)項(xiàng)（多次出現(xiàn)的元素）：我們想要構(gòu)建一個(gè)包含與列表 1 相同元素的列表 2咬腕，但是列表 2 中每個(gè)元素只重復(fù)出現(xiàn)一次欢峰。

例如，列表 1 里有以下元素：

AABCDBCA

則列表 2 將包含以下元素：

ABCD

你想到解決這個(gè)問題的算法了嗎涨共？在閱讀我的解決方案之前纽帖，請(qǐng)自己思考一下。

我的解決方案

我的算法如下：

對(duì)于給定的包含重復(fù)元素的列表 L举反，我們要構(gòu)建一個(gè)新的列表 U（取英語 Unique（“獨(dú)一無二的”）的第一個(gè)字母）懊直，列表 U 一開始是空的，我們需要往里面填充元素火鼻。
我們遍歷列表 L室囊，對(duì)于列表 L 中的每一個(gè)元素，我們確認(rèn)一下它是否存在于列表 U 中（可以用與之前的查找最大元素類似的算法魁索，畢竟就是逐一比較元素嘛）融撞。
如果列表 L 中遍歷到的元素還不在列表 U 中，就將這個(gè)元素添加進(jìn)列表 U 中粗蔚；如果已經(jīng)存在于列表 U 中尝偎，就不添加。
遍歷完列表 L 后鹏控，列表 U 中就擁有了和列表 L 相同的元素致扯，只是這些元素都是不重復(fù)出現(xiàn)的。

練習(xí)： 使用你喜歡的編程語言來實(shí)現(xiàn)上述從列表中提取不重復(fù)元素的算法当辐。

復(fù)雜度

這個(gè)算法的復(fù)雜度是多少抖僵？如果你充分理解了之前查找列表最大值的算法的復(fù)雜度的計(jì)算，那么這對(duì)你來說應(yīng)該很簡單缘揪。

對(duì)于給定列表 L 中的每個(gè)元素耍群，我們都會(huì)執(zhí)行遍歷列表 U 的操作，因此執(zhí)行的操作數(shù)與列表 U 包含的元素?cái)?shù)目有關(guān)寺晌。

但問題是：列表 U 的大小在遍歷給定列表 L 的過程中會(huì)發(fā)生變化世吨，因?yàn)槲覀儠?huì)添加元素進(jìn)列表 U澡刹。當(dāng)我們遍歷到列表 L 中的第一個(gè)元素時(shí)呻征，列表 U 還是空的（因此我們不執(zhí)行任何比較操作）；當(dāng)我們遍歷到列表 L 的第二個(gè)元素時(shí)罢浇，列表 U 有 1 個(gè)元素陆赋，所以我們要再執(zhí)行一個(gè)比較操作沐祷。

但是當(dāng)我們遍歷到列表 L 中的第三個(gè)元素時(shí)，我們就變得不是那么肯定了：如果列表 L 中的前兩個(gè)元素是不相同的攒岛，它們都被添加到 U 中赖临，在這種情況下我們要執(zhí)行 2 次比較操作（將列表 L 中的第三個(gè)元素分別與列表 U 中的兩個(gè)元素作比較）；如果前兩個(gè)元素是相同的灾锯，那么列表 L 中的第二個(gè)元素就沒有被添加到列表 U 中兢榨，只執(zhí)行 1 次比較操作。

正如我們的課程里已經(jīng)說過的顺饮，復(fù)雜度的計(jì)算需要考慮在“最壞的情況”（worst case）下：也就是執(zhí)行的操作數(shù)目最多時(shí)的復(fù)雜度吵聪。因此，我們將認(rèn)為給定列表 L 的所有元素都是不相同的兼雄。

在“最壞的情況”下吟逝，我們將給定列表 L 的所有元素逐一添加進(jìn)列表 U 中。假設(shè)給定列表 L 一共有 N 個(gè)元素赦肋，在遍歷到給定列表 L 的第 N 個(gè)元素時(shí)块攒，我們已經(jīng)向列表 U 添加了 (N-1) 個(gè)元素了，因此這時(shí)要做 (N-1) 次比較操作佃乘。

所以我們總共要做的比較操作數(shù)是 0 + 1 + 2 + ... + (N-1) 囱井。開始時(shí)的操作數(shù)少，越到后面做的操作越多（有點(diǎn)像人生趣避，出生時(shí)責(zé)任比較少琅绅，慢慢地責(zé)任越來越大，要處理的事情也越來越多鹅巍，不過也說明你在成長千扶，畢竟“能者多勞”）。

上面這一串?dāng)?shù)字相加骆捧，得到的總操作數(shù)是 N * (N - 1) / 2（這個(gè)不難澎羞，是數(shù)學(xué)里面的等差數(shù)列求和公式），由于我們?cè)谟?jì)算復(fù)雜度時(shí)考慮的是 N 很大的情況敛苇，上面的結(jié)果可以約等于 N * N / 2妆绞，即 N² / 2 個(gè)操作。

因此枫攀，我們的算法具有 O(N²) 的時(shí)間復(fù)雜度（我們?nèi)コ顺?shù)因子 1/2）括饶。我們也可以稱 O(N²) 為“二次/平方”的復(fù)雜度（正如我們稱 O(N) 具有“線性”的復(fù)雜度）。

與之前那個(gè)查找最大元素的算法比起來来涨，現(xiàn)在這個(gè)算法除了速度較慢（時(shí)間復(fù)雜度較高）之外图焰，還具有更高的空間復(fù)雜度：我們構(gòu)建了一個(gè)最初不存在的列表 U（因此申請(qǐng)了內(nèi)存空間）。

在最壞的情況下蹦掐，列表 U 還具有與給定列表 L 一樣多的元素：因此將為 N 個(gè)元素分配空間技羔，這使得空間復(fù)雜度為 O(N)僵闯。之前查找最大元素的算法的空間復(fù)雜度是恒定的（O(1)），但現(xiàn)在這個(gè)算法的空間復(fù)雜度卻是線性的（O(N)）藤滥。

該算法只需要比較元素鳖粟，因此被操作的元素并不一定要是整數(shù)：我們可以用相同的算法來消除單詞列表中重復(fù)的單詞，重復(fù)的浮點(diǎn)數(shù)拙绊，等等向图。因此，許多算法是與使用的元素的具體類型無關(guān)的标沪。

4. 尋找不重復(fù)的元素：另一種方法

尋找不重復(fù)的元素张漂，其實(shí)還有另一種算法（聰明如你可能也想到了）：我們可以先對(duì)給定列表 L 中的元素進(jìn)行排序，使得所有重復(fù)的元素都相鄰谨娜，這樣排除重復(fù)元素將變得很簡單航攒。

比如給定列表 L 初始是這樣的：

AABCDBCA

我們可以在構(gòu)建列表 U 前，先對(duì)列表 L 進(jìn)行排序趴梢，使其變成下面這樣：

AAABBCCD

這樣漠畜，我們之后構(gòu)建列表 U 的算法就簡單了。

算法如下：
只需遍歷排序后的列表 L坞靶，并記住最近一次遍歷到的那個(gè)元素憔狞。如果當(dāng)前元素與前一個(gè)元素相同，則這個(gè)元素是重復(fù)的彰阴，就不要把它包含在不重復(fù)元素的列表 U 中瘾敢。

如果重復(fù)的元素彼此不相鄰，則上述算法不再有效尿这。因此我們必須先對(duì)列表進(jìn)行排序簇抵。

這個(gè)新的算法的時(shí)間復(fù)雜度是什么？消除重復(fù)是在列表的單次遍歷中完成的射众，因此是線性的（ O(N)）碟摆。但由于我們必須先對(duì)列表進(jìn)行排序，因此第一步排序的操作也必須被考慮進(jìn)這種新算法的總復(fù)雜度中叨橱。

當(dāng)然了典蜕，在這里提到列表的排序還稍微有一些太早了，因?yàn)槲覀冊(cè)谥蟮恼n程里才會(huì)講到排序算法罗洗。

盡管目前我們還沒有學(xué)習(xí)排序算法和它們的復(fù)雜度愉舔，但我還是想說一下這個(gè)新算法的復(fù)雜度問題。

事實(shí)證明伙菜，這種算法的復(fù)雜度取決于排序的復(fù)雜度：因?yàn)樾停判蚧旧蠒?huì)執(zhí)行 N² 個(gè)操作，這遠(yuǎn)遠(yuǎn)超過我們之后的構(gòu)建列表 U 時(shí)的 N 個(gè)操作，所以整體復(fù)雜度是 O(N²)典奉。

然而躺翻，也存在更高端的排序算法丧叽，雖然仍然執(zhí)行多于 N 個(gè)操作卫玖，但比 N² 要少得多。

我們將在之后的課程里學(xué)習(xí)排序算法踊淳，目前你只需要知道這個(gè)多了一步排序的新算法比舊算法更有效假瞬，也更“高級(jí)”。

“在列表中搜索指定元素”與“找出列表中最大/小值的元素”是非常相似的算法迂尝，都是線性時(shí)間的（算法的時(shí)間復(fù)雜度是 O(N)）脱茉，空間復(fù)雜度都是 O(1)。

消除列表中的重復(fù)元素的算法更復(fù)雜一些垄开，因?yàn)樽詈唵蔚乃惴ㄔ跁r(shí)間上具有平方的時(shí)間復(fù)雜度（O(N²)）琴许，其空間復(fù)雜度具有線性（O(N)）。

我希望這些更具體的研究能讓你確信算法學(xué)和算法復(fù)雜度還是很有用的「榷悖現(xiàn)在你也應(yīng)該已經(jīng)習(xí)慣“算法”榜田，“時(shí)間復(fù)雜度”，“空間復(fù)雜度”這些基本概念了锻梳。

下一課開始箭券，我們要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)了，這樣我們就能把數(shù)據(jù)結(jié)構(gòu)和算法相結(jié)合并融會(huì)貫通了疑枯，畢竟這一對(duì)“活寶”是休戚相關(guān)的辩块。

5. 第一部分第六課預(yù)告

今天的課就到這里，一起加油吧荆永！

下一課：數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第六課：數(shù)組和鏈表（上）

我是 謝恩銘废亭，公眾號(hào)「程序員聯(lián)盟」（微信號(hào)：coderhub）運(yùn)營者，慕課網(wǎng)精英講師 Oscar 老師具钥，終生學(xué)習(xí)者滔以。
熱愛生活，喜歡游泳氓拼，略懂烹飪你画。
人生格言：「向著標(biāo)桿直跑」