數據結構和算法導論

計算機科學是通過使用計算機解決各種問題的研究領域。
為了使用計算機解決給出的問題，您需要為其設計算法。
可設計多個算法來解決特定的問題。
提供了最大效率的算法應用于解決此問題。
算法的效率可通過使用合適的數據結構來改善。
數據結構幫助創建簡單、可重用和易于維護的程序。
本模塊允許學員選擇并實現合適的數據結構和算法來解決特定的編程問題。

解決問題時算法和數據結構的作用

問題解決是每個科學規律的必要部分。
計算機廣泛用于解決與各個域有關的問題，例如銀行、商業、醫療、制造和運輸。
為了使用計算機解決給出的問題，您需要為其編寫程序。
程序由兩個組件組成，即算法和數據結構。

算法這個詞來源于波斯數學名稱Al-Khowarizmi。
算法可定義為解決問題的逐步程序。
算法幫助用戶在有限的步驟中到達正確的結果。

算法具有5個重要的屬性：
有限性
明確性(確定目的)
輸入
輸出
有效性

只要可以為其編寫算法，通過使用計算機可以解決問題。
此外，算法提供了以下好處：
幫助編寫對應的程序
幫助區分一系列可以解決的小問題和難以解決的問題
決策制定成為更加理性的過程
使得過程一致和可靠

數據結構的作用

可使用不同的算法來解決相同的問題。
一些算法可能比其它算法更有效地解決問題。
應使用提供最大效率的算法來解決問題。
改善算法效率的其中一個基本技巧是使用適當的數據結構。
數據結構被定義為在內存中互相組織各個數據元素的方式。

數據可以按許多不同的方式來組織。因此，您可以創建盡可能多的數據結構。
經過多年已經證明很有用的一些數據結構是：
?數據類型也是基本數據結構.
數組
鏈表
堆棧
隊列
樹
圖

合適數據結構的使用有助于提高程序的效率。
使用合適的數據結構還允許您克服一些其它編程挑戰，如：
簡化復雜的問題
創建標準的可重用的代碼組件
創建易于理解和維護的程序

數據結構的類型

數據結構可分為以下兩類：
靜態：例子–數組
動態：例子–鏈接表

設計算法時兩個常用的技巧是：
分治法
貪婪法

分治法是解決概念性困難問題的強大方法。
分治法需要你找出一個方法：
將問題細分為子問題
解決微不足道的用例
組合到子問題的解決方案以解決原始問題

基于貪婪法的算法用于解決優化問題，其中您需要在給定的條件集合中最大化利潤或最小化成本。
優化問題的一些示例包括：
找出從始發城市到一組目標城市的最短距離，給出兩個城市之間的距離。
找出某個金額所需的貨幣票據的最小數值，其中有每個命名的任意票據數。
從給出的項集合中選擇具有最大值的項，其中所選項的總重量不能超過給出的值。

遞歸：
遞歸指的是按照本身定義過程的技巧
用于解決本來重復的復雜編程問題
通過使用遞歸程序或函數，遞歸可以在程序中實現。遞歸程序或函數是調用本身的函數。
遞歸的主要好處是可用于編寫清晰、簡短和簡單的程序
最簡單的一個小例子：從前有座山，山里有個老和尚，….

課間思考

明確在嘗試找出前面n個自然數之和的以下算法中的問題：
????? 算法：Sum (n)
????? 1. s = n + Sum(n – 1)
????? 2. Return (s)

答案：
在給出的遞歸算法中沒有結束條件。因此，可以無限調用自身。正確的算法為：
????

??1. If (n = 1)
????? Return(1)
? 2. s = n + Sum(n – 1)
? 3. Return(s)

確定算法的效率

影響程序效率的因素包括：
機器速度
編譯器
操作系統
編程語言
輸入大小
除了這些因素，程序的方式數據被組織且用于解決此問題的算法還對程序的效率具有重大影響。

通過確定消耗的資源量，可以計算算法的效率。
算法消耗的主要資源是：
時間：執行算法所需的CPU時間。
空間：執行算法時所用的內存量。
算法使用的資源越少，效率越高。

時間/空間權衡：
指的是您可以在程序執行速度較慢時可以減少使用的內存或在使用內存的成本很高時減少運行的時間。
可以應用時間/空間權衡的情形示例為數據存儲。
內存是可擴展的，但時間卻不可以。因此，通常考慮時間要比考慮內存的情況多。

為了測量算法的時間效率，您可以根據算法編寫程序，執行程序并測量運行程序所需的時間。
您按這種方式測量的執行時間將取決于大量因素，例如：
機器的速度
編譯器
操作系統
編程語言
輸入數據
但是，您要確定執行時間是如何受算法的性質影響的。

算法的運行時間直接與算法中涉及的關鍵比較成比例，并且它是n的函數，其中n是輸入數據的大小。
算法的運行時間隨著輸入數據量的增加而增加的速率稱為算法增長的階。
算法增長的階使用大O符號來定義。
大O 符號已經接受為說明算法效率的基礎技巧。

增長的階與其對應的大O符號之間的不同是：
常量- O(1)
對數- O(log n)
線性 - O(n)
重對數- O(n log n)
二次方程- O(n2)
立方- O(n3)
指數- O(2n), O(10n)

根據增長階，大O 符號可按照遞增階的方式排列：
???? O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
???? < O(10n)

分組討論：所選算法的效率依賴性
問題描述：
您需要編寫算法以搜索字典中給定的單詞。討論組織致電數據的不同算法和不同方式如何影響進程的效率。

小結

在本章中，你已經學到：
算法可定義為解決問題的逐步程序，在有限的步驟內產生正確的結果。
算法具有5個重要的屬性：
有限性
明確性
輸入
輸出
有效性
提供了最大效率的算法應用于解決此問題。

數據結構可分為以下兩類：
靜態
動態
設計算法時兩個常用的技巧是：
分治法
貪婪法
遞歸指的是按照本身定義過程的技巧。用于解決本來重復的復雜編程問題。
算法消耗的主要資源是：
時間：執行算法所需的CPU時間。
空間：執行算法所用的內存量。

時間/空間權衡指的是您可以為了減慢程序執行的速度而減小內存的使用量，或在減少運行時間的同時提高使用的內存。
算法的總運行時間直接與算法中涉及的比較次數成比例。
算法增長的階使用大O符號來定義。