算法無處不在

當(dāng)我們聽到“算法”這個(gè)詞時(shí)，很自然地會(huì)想到數(shù)學(xué)。然而實(shí)際上，許多算法并不涉及復(fù)雜數(shù)學(xué)，而是更多地依賴于基本邏輯，這些邏輯在我們的日常生活中處處可見。

在正式探討算法之前，有一個(gè)有趣的事實(shí)值得分享：你已經(jīng)在不知不覺中學(xué)會(huì)了許多算法，并習(xí)慣將它們應(yīng)用到日常生活中了。下面，我將舉幾個(gè)具體例子來證實(shí)這一點(diǎn)。

例一：查閱字典。在字典里，每個(gè)漢字都對(duì)應(yīng)一個(gè)拼音，而字典是按照拼音字母順序排列的。假設(shè)我們需要查找一個(gè)拼音首字母為 r 的字，通常會(huì)按照?qǐng)D 1-1 所示的方式實(shí)現(xiàn)。

1. 翻開字典約一半的頁數(shù)，查看該頁的首字母是什么，假設(shè)首字母為 m 。
2. 由于在拼音字母表中 r 位于 m 之后，所以排除字典前半部分，查找范圍縮小到后半部分。
3. 不斷重復(fù)步驟 1. 和 步驟 2. ，直至找到拼音首字母為 r 的頁碼為止。

圖 1-1   查字典步驟

查閱字典這個(gè)小學(xué)生必備技能，實(shí)際上就是著名的二分查找算法。從數(shù)據(jù)結(jié)構(gòu)的角度，我們可以把字典視為一個(gè)已排序的“數(shù)組”；從算法的角度，我們可以將上述查字典的一系列操作看作是“二分查找”。

例二：整理撲克。我們?cè)诖蚺茣r(shí)，每局都需要整理撲克牌，使其從小到大排列，實(shí)現(xiàn)流程如圖 1-2 所示。

1. 將撲克牌劃分為“有序”和“無序”兩部分，并假設(shè)初始狀態(tài)下最左 1 張撲克牌已經(jīng)有序。
2. 在無序部分抽出一張撲克牌，插入至有序部分的正確位置；完成后最左 2 張撲克已經(jīng)有序。
3. 不斷循環(huán)步驟 2. ，每一輪將一張撲克牌從無序部分插入至有序部分，直至所有撲克牌都有序。

圖 1-2   撲克排序步驟

上述整理撲克牌的方法本質(zhì)上是“插入排序”算法，它在處理小型數(shù)據(jù)集時(shí)非常高效。許多編程語言的排序庫函數(shù)中都存在插入排序的身影。

例三：貨幣找零。假設(shè)我們?cè)诔匈徺I了 69 元的商品，給了收銀員 100 元，則收銀員需要找我們 31 元。他會(huì)很自然地完成如圖 1-3 所示的思考。

1. 可選項(xiàng)是比 31 元面值更小的貨幣，包括 1 元、5 元、10 元、20 元。
2. 從可選項(xiàng)中拿出最大的 20 元，剩余 31?20=11 元。
3. 從剩余可選項(xiàng)中拿出最大的 10 元，剩余 11?10=1 元。
4. 從剩余可選項(xiàng)中拿出最大的 1 元，剩余 1?1=0 元。
5. 完成找零，方案為 20+10+1=31 元。

圖 1-3   貨幣找零過程

在以上步驟中，我們每一步都采取當(dāng)前看來最好的選擇（盡可能用大面額的貨幣），最終得到了可行的找零方案。從數(shù)據(jù)結(jié)構(gòu)與算法的角度看，這種方法本質(zhì)上是“貪心”算法。

小到烹飪一道菜，大到星際航行，幾乎所有問題的解決都離不開算法。計(jì)算機(jī)的出現(xiàn)使我們能夠通過編程將數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在內(nèi)存中，同時(shí)編寫代碼調(diào)用 CPU 和 GPU 執(zhí)行算法。這樣一來，我們就能把生活中的問題轉(zhuǎn)移到計(jì)算機(jī)上，以更高效的方式解決各種復(fù)雜問題。

Tip

如果你對(duì)數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)組和二分查找等概念仍感到一知半解，請(qǐng)繼續(xù)往下閱讀，這本書將引導(dǎo)你邁入數(shù)據(jù)結(jié)構(gòu)與算法的知識(shí)殿堂。