1.1 數據結構與算法

考點1 算法

1.算法的基本概念

算法是指一系列解決問題的清晰指令。

（1）算法的基本特征。

●可行性：針對實際問題而設計的算法，執行后能夠得到滿意的結果，即必須有一個或多個輸出，即使在數學理論上是正確的，如果在實際的計算工具上不能執行，則該算法也是不具有可行性的。

●確定性：是指算法中每一步驟都必須是有明確定義的。

●有窮性：是指算法必須能在有限的時間內做完。

●擁有足夠的信息：一個算法是否有效，還取決于為算法所提供的信息是否足夠。

（2）算法的基本要素。

算法一般由兩種基本要素構成：

●對數據對象的運算和操作；

●算法的控制結構，即運算和操作時間的順序。

算法中對數據的運算和操作：算法就是按解題要求從指令系統中選擇合適的指令組成的指令序列。因此計算機算法就是計算機能執行的操作所組成的指令序列。不同的計算機系統，指令系統是有差異的，但一般的計算機系統中包括的運算和操作有4類：算術運算、邏輯運算、關系運算和數據傳輸。

算法的控制結構：算法中各操作之間的執行順序稱為算法的控制結構。算法的功能不僅取決于所選用的操作，還與各操作之間的執行順序有關?；镜目刂平Y構包括順序結構、選擇結構和循環結構。

（3）算法設計的基本方法。

算法設計的基本方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。

2.算法復雜度

算法的復雜度主要包括時間復雜度和空間復雜度。

（1）算法的時間復雜度。

所謂算法的時間復雜度是指執行算法所需要的計算工作量。

一般情況下，算法的工作量用算法所執行的基本運算次數來度量，而算法所執行的基本運算次數是問題規模的函數，即：算法的工作量=f（n）

其中n表示問題的規模。該表達式表示隨著問題規模n的增大，算法執行時間的增長率和f（n）的增長率相同。

在同一個問題規模下，如果算法執行所需的基本運算次數取決于某一特定輸入時，可以用兩種方法來分析算法的工作量：平均性態分析和最壞情況分析。

（2）算法的空間復雜度。

算法的空間復雜度一般是指執行這個算法所需要的內存空間。算法執行期間所需要的存儲空間包括以下3個部分：

●算法程序所占的空間；

●輸入的初始數據所占的存儲空間；

●算法執行過程中所需要的額外空間。

在實際操作中，為了減少算法所占的存儲空間，通常采用壓縮存儲的技術，用于減少不必要的額外空間。

真考鏈接

考核概率為45%?？忌煊浽摽键c的內容，尤其是算法的概念，以及時間復雜度和空間復雜度的概念。