《Python算法教程》——第2章 基礎知識 2.1 計算領域中一些核心理念

本節書摘來自異步社群《python算法教程》一書中的第2章，第2.1節，作者[挪威]magnus lie hetland（赫特蘭）， 淩傑 譯，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

tracey：我不知道您在哪裡。

zoe：隐身術就是這樣——您應該聽說過的。

tracey：我可不認為這屬于基礎知識。

——選自《firefly》第14集台詞

在我們将注意力轉向本書主體内容，也就是那些數學技術、算法設計原則及經典算法之前，還必須先了解一些最基本的技術與原則。因為當您閱讀到後續章節時，至少應該非常清楚類似“無反向環路的權重有向圖”以及“Θ(n lg n)運作時間”這些詞句所表達的具體含義。同時，我們也理應要對python中一些基本資料結構的實作方式有個起碼的了解。

幸運的是，這些基本問題并非都很難掌握。本章主要将聚焦于兩個話題：首先是漸近記法（asymptotic notation），它主要關注的是運作時間的本質。再就是樹（tree）與圖（graph）這兩種資料結構在python中的實作方式。在這部分内容中，我們将為您介紹一些與程式運作時間有關的實用建議，以及應該如何避免一些基本的設計陷阱。不過，還是先讓我們來看看應該如何在特定抽象機制中描述算法的行為吧。

20世紀30年代中期，英國數學家alan turing公開發表了一篇題為《on computable numbers, with an application to the entscheidungsproblem》（其中譯版為《論可計算數及其在判定問題上的應用》）的論文，這篇論文在許多方面都奠定了現代計算機科學的理論基礎。如今，由他所提出的抽象裝置——圖靈機——已經成為了計算領域的理論核心。當然，這在很大程度上是因為該裝置本身非常簡單，而且容易掌握。圖靈機是一種非常簡單的抽象裝置，它能讀、能寫，并且能沿着一條無限長的紙帶移動。盡管圖靈機有着各種不同的具體實作，但每種實作都可以被視為一台有限狀态機：它由一個有限的狀态集（包括已完成部分）與各種用于觸發讀寫操作及不同狀态切換的潛在符号共同組成。我們可以把它們看作這些機器運作所需要的一組規則（例如，“當我們在狀态4的情況下遇到x，就向左移動一步，然後寫入一個y，并切換到狀态9。”）。盡管這些機器看上去非常簡單，但已經很讓人驚歎了。因為有了它們，人們在計算領域就幾乎無所不能了。

通常來說，所謂算法，實際上指的是一個執行過程，包含了能夠解決某個特定問題的有限步驟集（其中可能包含了一些循環和條件元素）。而圖靈機則是這個待解決問題的一種正規描述形式。這種形式通常被用于讨論解決該問題所需要的時間（這裡既可以指整體時間，也可以指可接受的時間，相關内容将在第11章中詳細讨論）。然而對于更細粒度上的算法效率分析來說，圖靈機恐怕就不再是我們的首選了，因為這時候相較于可滾動的紙帶，我們更需要的是一大塊可直接存取的記憶體。于是随機存取機就應運而生了。

盡管随機存取機這種描述形式使用起來會有點兒複雜，但其實我們隻需知道其能力極限在哪裡，不至于讓它影響我們的算法分析結果就可以了。簡而言之，該機器是從标準單處理器計算機簡化出來的一種抽象模型，它應該具備以下幾個屬性。

該機器上不會有任何形式的并發執行，它隻有在執行完一條指令後才能執行其他指令。

該機器上的所有标準基本操作，如算術運算、比較運算以及記憶體存取，所耗費的時間都是常數級的（盡管具體數值上會有所不同），同時它也沒有更複雜的基本操作，例如排序。

盡管計算機字（即word，其大小通常等于我們在常數時間内所能讀取的值）的字長是有限的，但必須足夠大，大到能滿足我們在解決問題過程中所有的記憶體編址的需求，此外還要加上一定比例的額外變量。

當然，在某些情況下，我們可能還會有一些更具體的要求，但就機器本身而言也就大緻如此了。

現在，相信我們已經對算法是什麼，以及運作它們的抽象硬體環境有了一點直覺的認知。下面我們來談談整個概念拼圖中的最後一塊：問題。就我們的目标而言，問題其實指的是輸入與輸出之間所存在的某種關系。事實上，我們還可以說得更精确一些：這裡所反映的是一組集合對之間的關系（數學意義上的）——在這裡，對于輸入來說，什麼樣的輸出是可接受的——并且借由指定這種關系的過程，我們的問題就會被确定下來。以排序問題為例，我們可以将其視為a、b兩個集合之間的關系。這兩個集合分别由一組序列組成。除了描述具體的排序過程外（該過程就是算法），我們還需要指定對于一個給定的輸入序列（集合a中的某個元素），什麼樣的輸出序列（集合b中元素）是可接受的。我們可以規定結果序列必須由輸入序列相同的元素組成，并且将以遞增順序排列（其中的每個元素始終大于或等于前一個元素）。在這裡，集合a中的元素（輸入序列）就被我們稱為問題執行個體。由此可見，關系本身實際上就是我們的問題。

當然，想要讓我們的機器有的放矢，我們還得對其輸入進行0、1編碼。盡管在這裡，我們無須去關心那些編碼的具體細節，但是其中的理念很重要，因為其運作時間複雜度（這正是下一節中所要介紹的）是基于知道了問題執行個體大小，這個大小可以簡單看成編碼它所需的記憶體大小。我們會發現，這通常與編碼自身的确切屬性沒有太大關系。