很多考生在備考2022年軟件設計師考試，希賽小編為大家整理了2022年軟件設計師考試知識點（六十五）：時間復雜度與空間復雜度，供考生備考復習。

時間復雜度與空間復雜度（★★★★★）

【考法分析】

1、本知識點的考查形式主要有：根據題干描述的情景，根據排序方法、算法邏輯或相關代碼，計算其時間復雜度或空間復雜度；根據遞歸式，計算其時間復雜度；下午題也會考查根據題干說明和代碼，指出時間復雜度。

【要點分析】

1、時間復雜度是指程序運行從開始到結束所需要的時間。通常分析時間復雜度的方法是從算法中選取一種對于所研究的問題來說是基本運算的操作，以該操作重復執行的次數作為算法的時間度量。一般來說，算法中原操作重復執行的次數是規模n的某個函數T(n)。由于許多情況下要精確計算T(n)是困難的，因此引入了漸進時間復雜度在數量上估計一個算法的執行時間。其定義如下：

如果存在兩個常數c和m，對于所有的n，當n≥m時有f(n)≤cg(n)，則有f(n)=O(g(n))。也就是說，隨著n的增大，f(n)漸進地不大于g(n)。例如，一個程序的實際執行時間為T(n)=3n3+2n2+n，則T(n)=O(n3)。

常見的對算法執行所需時間的度量：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

2、常見排序方法的時間復雜度和空間復雜度見知識點60介紹；

3、常見算法邏輯的時間復雜度：

（1）單個語句，或程序無循環和復雜函數調用：O(1)

（2）單層循環：O(n)；雙層嵌套循環：O(n2)；三層嵌套循環：O(n3)。

（3）樹形結構、二分法、構建堆過程：O(log2n)。

（4）堆排序、歸并排序：O(nlog2n)。

（5）所有不同可能的排列組合：O(2n)。

4、主定理求固定形式遞歸式的時間復雜度：

【備考點撥】

1、掌握常見排序算法的時間復雜度和空間復雜度；

2、掌握常見排序算法、常見算法邏輯（如循環）的時間復雜度；

3、了解主定理求取遞歸式的時間復雜度。