算法是什么

算法定義

「算法 algorithm」是在有限時間內(nèi)解決特定問題的一組指令或操作步驟，它具有以下特性。

• 問題是明確的，包含清晰的輸入和輸出定義。
• 具有可行性，能夠在有限步驟、時間和內(nèi)存空間下完成。
• 各步驟都有確定的含義，相同的輸入和運行條件下，輸出始終相同。

數(shù)據(jù)結(jié)構(gòu)定義

「數(shù)據(jù)結(jié)構(gòu) data structure」是計算機中組織和存儲數(shù)據(jù)的方式，具有以下設(shè)計目標。

• 空間占用盡量減少，節(jié)省計算機內(nèi)存。
• 數(shù)據(jù)操作盡可能快速，涵蓋數(shù)據(jù)訪問、添加、刪除、更新等。
• 提供簡潔的數(shù)據(jù)表示和邏輯信息，以便使得算法高效運行。

數(shù)據(jù)結(jié)構(gòu)設(shè)計是一個充滿權(quán)衡的過程。如果想要在某方面取得提升，往往需要在另一方面作出妥協(xié)。下面舉兩個例子。

• 鏈表相較于數(shù)組，在數(shù)據(jù)添加和刪除操作上更加便捷，但犧牲了數(shù)據(jù)訪問速度。
• 圖相較于鏈表，提供了更豐富的邏輯信息，但需要占用更大的內(nèi)存空間。

數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系

如圖 1-4 所示，數(shù)據(jù)結(jié)構(gòu)與算法高度相關(guān)、緊密結(jié)合，具體表現(xiàn)以下三個方面。

• 數(shù)據(jù)結(jié)構(gòu)是算法的基石。數(shù)據(jù)結(jié)構(gòu)為算法提供了結(jié)構(gòu)化存儲的數(shù)據(jù)，以及用于操作數(shù)據(jù)的方法。
• 算法是數(shù)據(jù)結(jié)構(gòu)發(fā)揮作用的舞臺。數(shù)據(jù)結(jié)構(gòu)本身僅存儲數(shù)據(jù)信息，結(jié)合算法才能解決特定問題。
• 算法通?？梢曰诓煌臄?shù)據(jù)結(jié)構(gòu)進行實現(xiàn)，但執(zhí)行效率可能相差很大，選擇合適的數(shù)據(jù)結(jié)構(gòu)是關(guān)鍵。

圖 1-4   數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系

數(shù)據(jù)結(jié)構(gòu)與算法猶如圖 1-5 所示的拼裝積木。一套積木，除了包含許多零件之外，還附有詳細的組裝說明書。我們按照說明書一步步操作，就能組裝出精美的積木模型。

圖 1-5   拼裝積木

兩者的詳細對應(yīng)關(guān)系如表 1-1 所示。

表 1-1   將數(shù)據(jù)結(jié)構(gòu)與算法類比為積木

值得說明的是，數(shù)據(jù)結(jié)構(gòu)與算法是獨立于編程語言的。正因如此，本書得以提供多種編程語言的實現(xiàn)。