為幫助考生備考軟考軟件設(shè)計師考試，希賽小編為大家整理了2022下半年軟件設(shè)計師知識點：算法基礎(chǔ)及常見算法，相信對大家備考會有幫助。

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

【考法分析】

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

【要點分析】

1、算法的特性：

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

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

（3）輸入（>=0）

（3）輸出（>=1）

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

2、分治法

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

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

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

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

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

4、回溯法

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

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

5、貪心法（用于求滿意解）

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

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

【備考點撥】

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

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