《算法基礎》——第1章 算法基礎知識 1.1 方法

本節書摘來自華章計算機《算法基礎》一書中的第1章，第1.1節，作者：（美）羅德·斯蒂芬斯（rod stephens）著，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

在開始算法學習之前，你需要一點背景知識。簡單地說，首先需要知道的是算法是完成某些事情的方法。它定義了用某個方法執行一個任務的步驟。

這個定義看起來足夠簡單，但是沒有人為了做一件十分簡單的工作而寫算法。沒有人寫指令來擷取數組中的第四個元素。這隻是假設這是一個數組定義的一部分，并且你知道怎麼去做（如果你知道如何在這個問題中使用程式設計語言）。

一般來說，人們隻是為了完成複雜的任務而寫算法。算法解釋了如何找到一個複雜代數問題的答案，如何在一個包含數千條街道的網絡中找到最短路徑，抑或是如何在數百個投資中找到最好的投資組合來使利益最大化。

本章介紹一些基本的算法概念。如果想從算法學習中獲得最大的收獲，就應該了解它們。

跳過這一章然後去學某個特定的算法似乎很有誘惑力，但是你至少應該浏覽一下這一章。請着重注意1.4.1節，因為對運作時間是否有良好了解意味着算法能否在數秒、數小時内完成任務，還是永遠不能完成任務。

為了盡可能地了解一個算法，你需要做出更多努力而非簡單地遵循它的步驟。你需要了解以下内容：

算法的行為： 它尋找出了最好的方法還是僅僅找出了一個可行的解決辦法？可能有多個最佳的解決方案嗎？是否有一個方法可以從其他解決方案中尋找到一個“最佳”解決方案？

算法的速度：這個算法是快還是慢？還是它通常是快的，但有時對于某些輸入慢？

算法的存儲要求：這個算法需要多大的存儲空間？這個大小合理嗎？這個算法是否需要數十億tb的存儲空間，比一台計算機可能有的存儲空間還多（至少對現在的計算機來說如此）？

算法設計主要使用的技巧：是否可以利用這些技術解決類似的問題？

這本書涵蓋了所有這些主題。然而，本書沒有試圖用數學的精确理論去涵蓋每一個算法的每一個細節。本書使用一種直覺的方法來解釋算法及其性能，但是本書沒有用嚴謹的細節去分析算法的性能。盡管這種細節分析的證明可能是有趣的，但它也可能讓人混亂，并且會占用大量的篇幅，提供了對大多數程式員來說不必要的細節。畢竟，這本書主要适用于需要完成工作的專業程式員。

本書把具有相關主題的算法歸在一章。有時這個主題是它們所執行的任務（排序、搜尋、網絡算法），有時是它們所使用的資料結構（連結清單、數組、散清單、樹），有時是它們使用的技巧（遞歸、決策樹、分布式算法）。粗看起來，這些分組似乎是任意的，但當你讀到這些算法的時候，可以看到它們很好地組合在一起。

除了這些類别，許多算法的基本主題跨越章節界限。例如，樹算法（第10、11和12章）往往是高度遞歸的（第9章）。連結清單（第3章）可用于建立數組（第4章）、散清單（第8章）、棧（第5章）和隊列（第5章）。引用和指針的概念可以用來建立連結清單（第3章）、樹（第10、11和12章）和網絡（第13和14章）。在閱讀時，請關注這些共同的線索。附錄a中總結了常見的政策，這些政策能使這些想法更容易被了解。