很多考生在備考2022年軟件設(shè)計(jì)師考試，希賽小編為大家整理了2022年軟件設(shè)計(jì)師考試知識(shí)點(diǎn)（六十六）：算法基礎(chǔ)及常見(jiàn)算法，供考生備考復(fù)習(xí)。

算法基礎(chǔ)及常見(jiàn)算法（★★★★★）

【考法分析】

1、本知識(shí)點(diǎn)的考查形式主要有：根據(jù)題干的情景描述，判斷所使用的算法策略；判斷算法相關(guān)描述是否正確；下午題也會(huì)考查根據(jù)題干說(shuō)明和代碼，判斷算法策略。

【要點(diǎn)分析】

1、算法的特性：

（1）有窮性：執(zhí)行有窮步之后結(jié)束。

（2）確定性：算法中每一條指令都必須有確切的含義，不能含糊不清。

（3）輸入（>=0）

（3）輸出（>=1）

（4）有效性(可行性)：算法的每個(gè)步驟都能有效執(zhí)行并能得到確定的結(jié)果。例如a=0，b/a就無(wú)效

2、分治法

（1）特征：把一個(gè)問(wèn)題拆分成多個(gè)小規(guī)模的相同子問(wèn)題，一般可用遞歸解決。

（2）經(jīng)典問(wèn)題：斐波那契數(shù)列、歸并排序、快速排序、矩陣乘法、二分搜索、大整數(shù)乘法、漢諾塔

3、動(dòng)態(tài)規(guī)劃法（用于求最優(yōu)解）

（1）特征：劃分子問(wèn)題（最優(yōu)子結(jié)構(gòu)），并把子問(wèn)題結(jié)果使用數(shù)組存儲(chǔ)，利用查詢(xún)子問(wèn)題結(jié)果構(gòu)造最終問(wèn)題結(jié)果。

（2）經(jīng)典問(wèn)題：斐波那契數(shù)列、矩陣乘法、背包問(wèn)題、 LCS最長(zhǎng)公共子序列

4、回溯法

（1）特征：系統(tǒng)的搜索一個(gè)問(wèn)題的所有解或任一解。有試探和回退的過(guò)程。

（2）經(jīng)典問(wèn)題：N皇后問(wèn)題、迷宮、背包問(wèn)題

5、貪心法（用于求滿(mǎn)意解）

（1）特征：局部最優(yōu)，但整體不見(jiàn)得最優(yōu)。每步有明確的，既定的策略。

（2）經(jīng)典問(wèn)題：背包問(wèn)題（如裝箱）、多機(jī)調(diào)度、找零錢(qián)問(wèn)題

【備考點(diǎn)撥】

1、掌握算法的特性、概念；

2、掌握常見(jiàn)算法的特點(diǎn)、適用場(chǎng)景，并能夠加以區(qū)分。