演算法/導論

頂部，章節：1，2，3，4，5，6，7，8，9，A

本書涵蓋了演算法設計和分析的技術。涵蓋的演算法技術包括：分治法、回溯法、動態規劃、貪心演算法和爬山法。

任何可解問題通常至少有一種以下型別的演算法

1. 顯而易見的方式；
2. 有條理的方式；
3. 巧妙的方式；並且
4. 神奇的方式。

在第一個也是最基本的層面上，“顯而易見”的解決方案可能會嘗試窮舉搜尋答案。直觀地說，如果您熟悉程式語言和基本問題解決技術，顯而易見的解決方案是易於想到的解決方案。

第二個級別是有條理的級別，也是本書的核心：在理解此處介紹的材料後，您應該能夠有條理地將大多數顯而易見的演算法轉變為效能更好的演算法。

第三級，巧妙的級別，需要更多地瞭解問題中涉及的元素及其屬性，甚至需要重新制定演算法（例如，數值演算法利用了不明顯的數學屬性）。一個巧妙的演算法可能難以理解，因為它不明顯它是正確的，或者可能難以理解它實際上比它看起來需要的執行速度更快。

演算法解決方案的第四個也是最後一個級別是神奇的級別：這保留了在突破導致高度非直觀的解決方案的罕見情況下。

當然，所有這四個級別都是相對的，除了有條理的技術外，本書還涵蓋了一些巧妙的演算法。讓我們開始吧。

先決條件

要理解本書中介紹的材料，您需要足夠了解一門程式語言，以便將本書中的虛擬碼轉換為有效的解決方案。您還需要了解以下資料結構的基礎知識：陣列、堆疊、佇列、連結串列、樹、堆（也稱為優先順序佇列）、不相交集和圖。

此外，您應該瞭解一些基本演算法，如二分查詢、排序演算法（歸併排序、堆排序、插入排序或其他演算法），以及廣度優先搜尋或深度優先搜尋。

如果您不熟悉這些先決條件中的任何一個，您應該首先複習資料結構一書中的材料。

什麼時候效率很重要？

並非每個問題都需要最有效的解決方案。就我們而言，術語效率與執行任務所需的時間和/或空間有關。當時間或空間充足且便宜時，可能不值得讓程式設計師花一兩天時間來使程式更快。

但是，以下是一些效率很重要的案例

• 當資源有限時，演算法的改變可以節省大量成本，並允許有限的機器（如手機、嵌入式系統和感測器網路）擴充套件到可能的極限。

• 當資料量很大時，更有效的解決方案可能意味著任務在兩天內完成與兩週內完成之間的區別。示例包括物理學、遺傳學、網路搜尋、大型線上商店和網路流量分析。

• 即時應用程式：術語“即時應用程式”實際上是指提供時間保證的計算，而不是“快速”。但是，透過選擇合適的演算法，可以進一步提高質量。

• 計算量大的工作，如流體動力學、偏微分方程、VLSI 設計和密碼分析，有時只有在找到足夠有效的解決方案時才能考慮。

• 當子程式是通用的並且經常使用時，在更有效的實現上花費的時間可以為使用該子程式的每個應用程式帶來好處。示例包括排序、搜尋、偽隨機數生成、核心操作（不要與作業系統核心混淆）、資料庫查詢和圖形。

簡而言之，當您沒有時間時，節省時間很重要。

什麼時候效率不重要？這些案例的示例包括僅使用幾次的原型、輸入量很小的案例、簡單性和易於維護比效率更重要的案例、所關注的區域不是瓶頸，或者程式碼中其他過程或區域將從高效的設計和對演算法的關注中獲得更多好處。

發明演算法

因為我們假設您瞭解某種程式語言，所以讓我們從如何將想法轉化為演算法開始。假設您想編寫一個函式，該函式將以字串作為輸入，並以小寫形式輸出字串

// tolower -- translates all alphabetic, uppercase characters in str to lowercase
function tolower(string str): string

當您想到解決這個問題時，您首先想到的是什麼？也許您腦海中浮現了這兩個考慮因素

1. 需要檢視str 中的每個字元
2. 需要將單個字元轉換為小寫例程

第一點是“顯而易見”的，因為需要轉換的字元可能出現在字串中的任何位置。第二點是從第一點得出的，因為一旦我們考慮了每個字元，我們就需要對其執行某些操作。有許多方法可以編寫字元的tolower函式

function tolower(character c): character

有幾種方法可以實現此函式，包括

• 在表中查詢c——一個字元索引陣列，其中包含每個字元的小寫版本。

• 檢查c 是否在範圍 'A' ≤ c ≤ 'Z' 內，然後向其新增數值偏移量。

這些技術取決於字元編碼。（作為關注點分離問題，也許表格解決方案更強大，因為它更清楚地表明您只需要更改程式碼的一部分。）

但是，無論以何種方式實現此子例程，一旦我們擁有它，我們原始問題的實現就會立即出現

// tolower -- translates all alphabetic, uppercase characters in str to lowercase
function tolower(string str): string
  let result := ""
  for-each c in str:
    result.append(tolower(c))
  repeat
  return result
end

此程式碼示例也可在Ada 中獲得。

迴圈是我們能夠將“需要檢視每個字元”轉換為我們的原生程式語言的結果。顯而易見的是，tolower 子程式呼叫應該在迴圈主體中。將高階任務轉換為實現所需的最後一步是決定如何構建生成的字串。在這裡，我們選擇從空字串開始，並將字元追加到它的末尾。

現在假設您想編寫一個用於比較兩個字串的函式，該函式測試它們是否相等，忽略大小寫

// equal-ignore-case -- returns true if s and t are equal, ignoring case
function equal-ignore-case(string s, string t): boolean

這些想法可能會出現在您的腦海中

1. 字串s 和t 中的每個字元都必須檢視
2. 一個遍歷兩者的單迴圈可以實現這一點
3. 但這樣的迴圈應該首先小心字串長度是否相等
4. 如果字串長度不同，則它們不可能相等，因為忽略大小寫並不影響字串的長度
5. 可以再次使用字元的 tolower 子程式，並且只比較小寫版本

這些想法來自您對字串以及語言中迴圈和條件構造的熟悉程度。您想到的函式可能類似於以下函式

// equal-ignore-case -- returns true if s or t are equal, ignoring case
function equal-ignore-case(string s[1..n], string t[1..m]): boolean
  if n != m:
    return false               \if they aren't the same length, they aren't equal\
  fi
  
  for i := 1 to n:
    if tolower(s[i]) != tolower(t[i]):
      return false
    fi
  repeat
  return true
end

此程式碼示例也可在Ada 中獲得。

或者，如果您從函式分解而不是迭代的角度考慮問題，您可能想到的函式更像這樣

// equal-ignore-case -- returns true if s or t are equal, ignoring case
function equal-ignore-case(string s, string t): boolean
  return tolower(s).equals(tolower(t))
end

或者，您可能覺得這兩個解決方案都不夠有效，並且您更喜歡只對s 或t 進行一次遍歷的演算法。以上兩個實現都需要兩次遍歷：第一個版本計算長度，然後比較每個字元，而第二個版本計算字串的小寫版本，然後將結果彼此比較。（請注意，對於一對字串，也可以預先計算長度以避免第二次遍歷，但這有時會有其自身的缺點。）您可以想象如何編寫類似的例程來測試字串相等性，這些例程不僅忽略大小寫，還忽略重音符號。

你現在可能已經開始理解本書中的虛擬碼了。虛擬碼語言並非真正的程式語言：它抽象掉了你必須在任何語言中都要處理的細節。例如，該語言不假設泛型或動態型別與靜態型別：它的理念是應該明確意圖，並且將其轉換為你的母語不應該太難。（但是，在這樣做的過程中，你可能需要做出一些設計決策，將實現限制為一種特定的型別或資料形式。）

到目前為止，我們用來解決這些簡單字串問題的技術沒有什麼特別的：這些技術可能已經在你的工具箱裡了，你可能已經找到了在你選擇的程式語言中表達這些解決方案的更好或更優雅的方法。在本書中，我們將探索更通用的演算法技術，以進一步擴充套件你的工具箱。將一個簡單的演算法改進成更高效的演算法可能並不那麼容易，但透過理解本書中的內容，你應該能夠有條不紊地應用不同的解決方案，最重要的是，你將能夠對自己程式提出更多問題。提問與回答一樣重要，因為提出正確的問題可以幫助你重新表述問題，跳出框框思考。

理解演算法

計算機程式設計師需要具備出色的多層抽象推理能力。例如，考慮以下程式碼

function foo(integer a):
  if (a / 2) * 2 == a:
     print "The value " a " is even."
  fi
end

要理解這個例子，你需要知道整數除法使用截斷，因此當 if 條件為真時，a 中的最低有效位為零（這意味著 a 必須為偶數）。此外，程式碼使用字串列印 API，它本身是一個由不同模組使用的函式的定義。根據程式設計任務，你可能需要考慮硬體層，一直到處理器分支預測或快取級別。

二進位制的理解通常至關重要，但許多現代語言的抽象已經遠離“硬體”，因此這些較低級別並不必要。抽象在某個地方停止：大多數程式設計師不需要考慮邏輯閘，電子物理也不必要。然而，多層思考是程式設計中必不可少的一部分。

但是，從計算機程式轉向演算法需要另一層：數學。一個程式可能利用二進位制表示的特性。一個演算法可以利用集合論或其他數學構造的特性。正如二進位制本身在程式中並不顯式一樣，演算法中使用的數學屬性也是不顯式的。

通常，當介紹一種演算法時，需要進行討論（與程式碼分離）來解釋該演算法使用的數學方法。例如，要真正理解貪心演算法（如 Dijkstra 演算法），你應該理解數學性質，這些性質表明貪心策略在所有情況下都是有效的。在某種程度上，你可以將數學視為演算法呼叫的自身的一種子程式。但這種“子程式”在程式碼中不存在，因為沒有可呼叫的東西。當你閱讀本書時，嘗試將數學視為一個隱式子程式。

技術的概述

本書涵蓋的技術在以下概述中突出顯示。

• 分治：許多問題，特別是當輸入以陣列的形式給出時，可以透過將問題分解成更小的部分（分）、遞迴地解決這些較小的部分（治），然後將這些解決方案合併成單個結果來解決。例如，歸併排序和快速排序演算法。

• 隨機化：越來越多的隨機化技術對於許多應用程式至關重要。本章介紹了一些使用隨機數的經典演算法。

• 回溯：幾乎任何問題都可以以某種形式表示為回溯演算法。在回溯中，你考慮所有可能的解決方案，並在假設已做出選擇的情況下遞迴地解決子問題。遞迴呼叫的集合生成一棵樹，其中樹中的每個選擇集合都會被依次考慮。因此，如果存在解決方案，它最終會被找到。

回溯通常是一種低效的蠻力技術，但有一些最佳化措施可以執行，以減少樹的深度和分支的數量。該技術被稱為回溯，因為在訪問樹的一個葉子節點之後，演算法將返回到呼叫堆疊（撤銷沒有導致成功的選擇），然後繼續沿著其他分支進行。要使用回溯技術解決問題，問題需要具有一定形式的“自相似性”，即問題（在做出選擇之後）的較小例項必須類似於原始問題。通常，問題可以概括為自相似的。

• 動態規劃：動態規劃是針對回溯演算法的最佳化技術。當子問題需要重複解決時（即，當回溯演算法中存在許多重複分支時），透過首先解決所有子問題（自下而上，從小到大）並將每個子問題的解決方案儲存在一個表中，可以節省時間。因此，每個子問題只訪問和解決一次，而不是重複解決。“規劃”一詞來自在表中記錄內容的意義；例如，電視節目編排是指在表中記錄哪些節目將在何時播出。

• 貪心演算法：當對可能的選項有足夠的瞭解，從而可以在不考慮所有可能選項的情況下確定“最佳”選項時，貪心演算法非常有用。通常，貪心演算法並不難寫，但很難證明其正確性。

• 爬山演算法：我們探索的最後一種技術是爬山演算法。基本思路是從問題的糟糕解決方案開始，然後反覆應用最佳化，直到找到最佳解決方案或滿足其他要求。爬山演算法的一個重要案例是網路流。儘管名稱如此，但網路流對於描述關係的許多問題都有用，因此不僅僅用於計算機網路。許多匹配問題可以使用網路流來解決。

---

頂部，章節：1，2，3，4，5，6，7，8，9，A

演算法和程式碼示例

一級（最簡單）

1. 查詢最大值 包含演算法和多種不同的程式語言

2. 查詢最小值 包含演算法和多種不同的程式語言

3. 查詢平均值 包含演算法和多種不同的程式語言

4. 查詢眾數 包含演算法和多種不同的程式語言

5. 查詢總和 包含演算法和多種不同的程式語言

6. 計數 包含演算法和多種不同的程式語言

7. 查詢平均值包含演算法和多種不同的程式語言

二級

1. 與計算機對話一級 包含演算法和多種不同的程式語言

2. 排序 - 氣泡排序 包含演算法和多種不同的程式語言

三級

1. 與計算機對話二級 包含演算法和多種不同的程式語言

四級

1. 與計算機對話三級 包含演算法和多種不同的程式語言

2. 查詢近似最大值 包含演算法和多種不同的程式語言

五級

1. 快速排序