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

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

【考法分析】

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

【要點(diǎn)分析】

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

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

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

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

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

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

（1）單個(gè)語(yǔ)句，或程序無(wú)循環(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、主定理求固定形式遞歸式的時(shí)間復(fù)雜度：

【備考點(diǎn)撥】

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

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

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