漫畫說演算法

1. 什麼是演算法演算法的特性有哪些

演算法，指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。

特徵：有窮性，演算法必須能在執行有限個步驟之後終止；確切性，演算法的每一步驟必須有確切的定義；輸入項，一個演算法有0個或多個輸入，以刻畫運算對象初始情況；輸出項，一個演算法有一個或多個輸出以反映對輸入數據加工後的結果；可行性，演算法中執行的任何計算步驟都可被分解為基本的可執行的操作步驟。

(1)漫畫說演算法擴展閱讀：

演算法可以宏泛分為三類：

1、有限的、確定性演算法：這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務，但仍將在一定的時間內終止。這類演算法得出的結果常取決於輸入值。

2、有限的、非確定演算法：這類演算法在有限的時間內終止。然而，對於一個（或一些）給定的數值，演算法的結果並不是唯一的或確定的。

3、無限的演算法：是那些由於沒有定義終止定義條件，或定義的條件無法由輸入的數據滿足而不終止運行的演算法。通常，無限演算法的產生是由於未能確定的定義終止條件。

2. 推薦一些關於演算法的書籍

1、數據結構與演算法分析：C語言描述（適合入門）

這本書相對於演算法導論要簡單一些，更適合入門。演算法導論其實有比較強的理論性，看起來比較吃力。

《數據結構與演算法分析:C語言描述》內容簡介：書中詳細介紹了當前流行的論題和新的變化，討論了演算法設計技巧，並在研究演算法的性能、效率以及對運行時間分析的基礎上考查了一些高級數據結構，從歷史的角度和近年的進展對數據結構的活躍領域進行了簡要的概括。由於《數據結構與演算法分析:C語言描述(原書第2版)》選材新穎，方法實用，題例豐富，取捨得當。《數據結構與演算法分析:C語言描述》的目的是培養學生良好的程序設計技巧和熟練的演算法分析能力，使得他們能夠開發出高效率的程序。從服務於實踐又鍛煉學生實際能力出發，書中提供了大部演算法的C程序和偽碼常式。

2、演算法設計與分析基礎（適合入門）

作者基於豐富的教學經驗，開發了一套對演算法進行分類的新方法。這套方法站在通用問題求解策略的高度，能對現有的大多數演算法都能進行准確分類，從而使本書的讀者能夠沿著一條清晰的、一致的、連貫的思路來探索演算法設計與分析這一迷人領域。本書作為第2版，相對第1版增加了新的習題，還增加了「迭代改進」一章，使得原來的分類方法更加完善。

3.0、演算法引論：一種創造性方法（適合入門）

和普通的演算法書不同，這本書從創造性的角度出發——如果說演算法導論講的是有哪些演算法，那麼演算法引論講的就是如何創造演算法。結合前面的演算法設計與分析基礎，這本書把能解決的演算法問題數量擴大了一個數量級。

3.1 演算法競賽 | 信息學奧賽一本通（算競入門）

AlphaWA同學推薦的入門書籍，網上沒有PDF版本，自己去淘寶買嘍。

3.2 演算法競賽 | 演算法競賽進階指南（算競進階）

3. 關於ACM的動漫會是什麼樣

《演算法少女野崎君》：一直喜歡的男生竟然是ACM金牌得主！什麼！讓我加他們隊! 《黑子的演算法》：曾經我們是雄霸一方的ACM戰隊，最終升學到了不同的學校，因為隊長對勝利的執迷，他們都不是最初的他們了，所以我要寫出更厲害的代碼更精準的演算法，在ACM比賽中打贏他們，讓他們知道隊長你的信念是不對的！火神你會幫我吧？ 《Free！》：曾經一起愉快的學編程！最後你竟然只愛編程不參加ACM比賽！浪費才華！我一定不會輸給你！ 《Fate系列》：為了爭奪最後的ACM金牌！master！我來幫你寫演算法！ 《櫻蘭高校ACM部》：一個天然的演算法天才少女誤入櫻蘭ACM競賽碼神俱樂部 《ACM特優生》：為啥男主代碼寫的永遠比我短小精悍健壯性高。

4. 漫畫演算法--小灰的演算法之旅

人們常說演算法是程序員的內功，
我也覺得這是每個程序員的必修課。
演算法注重效率和節約空間，
如何更優更優雅的解決問題。
相對來說是比較難而且比較枯燥的，
這本書生動形象的解釋了常用的數據結構以及排序方法，
後面還有常用演算法部分講解，
是入門的比較不錯的書之一。

這本書也是同樣缺點就是不夠深入，
適合入門，如果想繼續深究還需要看更多的書。
整體來說還是比較不錯的比較簡單易懂。

5. 《漫畫演算法》—— 【3】樹

在樹的結構中，樹的定義如下。
樹（tree）是n（n>=0）個節點的有限集，當n=0時，稱為空樹。在任意一個非空樹中，有如下特點：

1、有且僅有一個特定的稱為根的節點。
2、當n>1時，其餘節點可分為m(m>0)個互不相交的有限集，每一個集合本身又是一個樹，並稱為根的子樹。

【相關節點】

樹的最大層級樹，被稱為樹的高度或深度。

樹的每個節點最多有2個孩子節點。
樹的一種特殊形式。樹的每個節點 最多有2個孩子節點 。

二叉樹的兩個孩子節點，一個被稱為 左孩子 ，一個被稱為 右孩子 。這兩個孩子節點的順序是固定的。

二叉樹有兩種特殊形式：滿二叉樹、完全二叉樹。

滿二叉樹 ：一個二叉樹的所有非葉子節點都存在左右孩子，並且所有葉子節點都在同一層接上。簡言之，滿二叉樹的每一個分支都是滿的。

完全二叉樹 ：對一個有n個節點的二叉樹，按層級順序編號，則所有節點的編號為從1到n。如果這個樹所有節點和同樣深度的滿二叉樹的編號為從1到n的節點位置相同，則這個二叉樹為完全二叉樹。

一棵樹，若為滿二叉樹，那麼一定是完全二叉樹。反之，不一定。

在內存中存儲 ：

為什麼這么設計？可以更方便的定位孩子節點、父節點。
若父節點的下標是parent，那麼左孩子節點下標是2 parent+1，右孩子節點下標是2 parent+2。
反之，若左孩子節點下標是leftChild,那麼父節點下標是(leftChild - 1)/2。
稀疏二叉樹，用數組表示會很浪費空間。

二叉樹的應用：查找操作、維持相對順序。

1、查找

二叉查找樹在二叉樹的基礎上增加了以下幾個條件：

如果左子樹不為空，則左子樹上所有節點的值均小於根節點的值；
如果右子樹不為空，則右子樹上所有節點的值均大於根節點的值；
左、右子樹也都是二叉查找樹。

對於一個節點分布相對均衡的二叉查找樹來說，如果節點總數是n，那麼搜索節點的 時間復雜度都是O(logn) ，和樹的深度是一樣的。

2、維持相對順序（插入）

二叉查找樹的特性保證了二叉樹的有序性，因此還有另外一個名字：二叉排序樹。

插入的過程中，可能會出現需要二叉樹進行自平衡，例如下圖的情況：

如圖所示，不只是樹的外觀看起來怪異，查詢節點的時間復雜度也退化成了O(n)。

二叉樹的自平衡的方式有很多種，如紅黑樹、AVL樹、樹堆等。

二叉樹的遍歷：
從節點之間位置關系的角度：
* 前序遍歷：輸出順序：根節點、左子樹、右子樹
* 中序遍歷：輸出順序：左子樹、根節點、右子樹
* 後序遍歷：輸出順序：左子樹、右子樹、根節點
* 層序遍歷：按照從根節點到葉子節點的層級關系，一層一層橫向遍歷各個節點。

從更宏觀的角度:
* 深度優先遍歷(前、中、後序遍歷，前中後是相對根節點)
* 廣度優先遍歷(層序遍歷)

二叉堆：本質上是一種完全二叉樹。
二叉堆本質上是一種完全二叉樹，分為2個類型：

最大堆 ：任何一個父節點的值，都大於或等於它左、右孩子節點的值；
最小堆 ：任何一個父節點的值，都小於或等於它左、右孩子節點的值。
二叉堆的根節點，叫作 堆頂 。最大堆的堆頂是整個堆中最大元素，最小堆的堆頂是整個堆中最小元素。
二叉堆雖然是一個完全二叉樹，但它的存儲方式並不是鏈式存儲，而是順序存儲，如下圖所示：

假設父節點的下標是parent，那麼它的左孩子的下標就是 2 * parent + 1 ，右孩子的下標就是 2 * parent + 2 。

二叉堆的3種操作（假設是最小堆）：
1、插入節點：時間復雜度O(logn)
插入節點是通過「上浮」操作完成的：當二叉堆插入節點時，插入位置是完全二叉樹的最後一個位置，將該節點與它的父節點進行比較，如果該節點小於它的父節點，那麼該與它的父節點交換位置，直到比較到堆頂位置。
2、刪除節點：時間復雜度O(logn)
刪除節點是通過「下沉」操作完成的：將要刪除的節點看作是堆頂，只看該節點及它下面的部分。因為堆頂元素要進行刪除，將最後一個節點元素替換堆頂元素，將替換後的元素與它的左、右子樹進行比較，如果左、右孩子節點中最小的一個比該節點小，那麼該節點「下沉」，直到葉子節點。
3、構建二叉堆：時間復雜度O(n)
構建二叉堆，也就是把一個無序的完全二叉樹調整為二叉堆，本質就是讓所有非葉子節點一次「下沉」。

優先隊列不再遵循先入先出的原則，而是分為兩種情況：

最大優先隊列 ，無論入隊順序如何，都是當前最大的元素優先出隊；
最小優先隊列 ，無論入隊順序如何，都是當前最小的元素優先出隊。

二叉堆節點的「上浮」和「下沉」的時間復雜度都是O(logn)，所以優先隊列入隊和出隊的時間復雜度也是O(logn)。

https://blog.csdn.net/qq_28958301/article/details/91590545

6. 什麼叫演算法

演算法，對應的英文單詞是algorithm，這是一個很古老的概念，最早來自數學領域，是用於解決某一類問題的公式和思想。

計算機科學領域的演算法，本質是一系列程序指令，用於解答特定的運算和邏輯問題。一般運用時間復雜度和空間復雜度來衡量演算法好壞。

演算法的應用領域多種多樣：

• 運算，例如計算兩個數的最大公約數。

• 查找，例如使用谷歌、網路搜索某一關鍵詞得出數據和信息。

• 排序：例如瀏覽電商網站時，商品按價格從低到高進行排序。

• 最優決策：例如游戲中讓AI角色找到迷宮的最佳路線。

參考資料：魏夢舒（@程序員小灰）,《漫畫演算法：小灰的演算法之旅》:電子工業出版社，2019-05