為幫助考生備考軟考軟件設(shè)計師考試，希賽小編為大家整理了2022下半年軟件設(shè)計師知識點(diǎn)：時間復(fù)雜度與空間復(fù)雜度，相信對大家備考會有幫助。

時間復(fù)雜度與空間復(fù)雜度（★★★★★）

【考法分析】

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

【要點(diǎn)分析】

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

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

常見的對算法執(zhí)行所需時間的度量：

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

2、常見排序方法的時間復(fù)雜度和空間復(fù)雜度見知識點(diǎn)60介紹；

3、常見算法邏輯的時間復(fù)雜度：

（1）單個語句，或程序無循環(huán)和復(fù)雜函數(shù)調(diào)用：O(1)

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

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

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

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

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

【備考點(diǎn)撥】

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

2、掌握常見排序算法、常見算法邏輯（如循環(huán)）的時間復(fù)雜度；

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