1.1 數據結構與算法

考點1 算法

真考鏈接

在選擇題中，考核概率為45%。該知識點屬于熟記內容，應熟記算法、時間復雜度和空間復雜度的概念。

1.算法的基本概念

算法是指解題方案的準確而完整的描述。

（1）算法的基本特征

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

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

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

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

（2）算法的基本要素

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

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

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

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

算法的控制結構：算法中各操作之間的進行順序稱為算法的控制結構。算法的功能不僅取決于所選用的操作，還與各操作之間的進行順序有關。基本的控制結構包括順序結構、選擇結構和循環結構等。

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

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

2.算法復雜度

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

（1）算法的時間復雜度

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

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

算法的工作量=f（n）

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

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

（2）算法的空間復雜度

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

●算法程序所占的空間；

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

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

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