2024年软件设计师中级（软考中级）详细笔记【8】算法设计与分析（分值4~5）

🕗 发布于 2024-10-20 09:51 算法笔记 java c语言 学习方法

前言

在备考软件设计师中级考试的过程中，我遇到了些许挑战，也收获了宝贵的经验。为了帮助其他同样正在为这门考试（证书）奋斗的朋友们，我决定将我的笔记整理出来，与大家分享。这些笔记不仅包含了书本上的知识，还加入了我对重点和难点的个人理解以及考试技巧，力求帮助大家更加高效地复习。我希望这份笔记能够成为你备考路上的一份支持，也祝愿你在考试中取得理想的成绩👍👍👍

如果有写的不好或者需要改进的地方，恳请在评论区指正！🤓🤓🤓

第8章算法设计与分析（4~5分）

8.1 算法设计与分析的基本概念

8.1.1 算法

有穷性
确定性
可行性
输入
输出

8.2 算法分析继承

8.2.0 大O表示法

算法时间复杂度以算法中基本操作重复执行的次数（简称为频度）作为算法的时间段量。一般不必要精确计算出算法的时间复杂度，只要大致计算出相应的数量级即可，如O(1）、O(log₂n)、 O(n)或O(n²)等。
图3-1 大O表示法

常对幂指阶

加法规则：多项相加，保留最高阶项，并将系数化为1；O(f(n))+ O(g(n)) = O(max(f(n), g(n)))
乘法规则：多项相乘都保留，并将系数化为1；O(f(n)) x O(g(n)) = O(f(n) x g(n))
加法乘法混合规则：小括号再乘法规则最后加法规则

8.2.1 时间复杂度

文3-1时间复杂度

结论1：顺序执行的代码只会影响常数项，可以忽略
结论2：只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
结论3：如果有多层嵌套循环，只需关注最深层循环循环了几次

三种复杂度

最坏时间复杂度
平均时间复杂度
最好时间复杂度

8.2.2 递归式时间复杂度

时间复杂度=递归的次数×每次递归的时间复杂度
空间复杂度=递归调用的深度

在这里插入图片描述

8.2.3 空间复杂度

在这里插入图片描述

8.2.4 渐进符号

在这里插入图片描述

8.2.5 递归式

8.2.5.1 展开法域代换法

记住对应公式与时间复杂度
在这里插入图片描述

8.2.5.2 递归式主方法

主方法也称为主定理，给出了求解以下形式的递归式的快速方法
【要记住公式】

T(n)=aT(n/b)+f(n)
8.1中的(1)(2)

8.3 分治法

快速排序属于分治法

一般来说，分治算法在每一层递归上都有3个步骤。
（1）分解。将原问题分解成一系列子问题。
（2）求解。递归地求解各子问题。若子问题足够小，则直接求解。
（3）合并。将子问题的解合并成原问题的解。

合并排序算法对n个元素进行排序所需的计算时间T(n)满足
$T(n)=\begin{cases} O(1),\quad n\leq1 \\ 2T(n/2)+O(n),\quad n>1 \end{cases}$

8.4 动态规划法

对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解。

最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。
重叠子问题。重叠子问题指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法逆归求解，则每次週到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

0-1 背包问题

时间复杂度和空间复杂度均为O(NW)
其中N是物品数量，W是背包容量。

不选第i个物品
- 等于f[i][j]=f[i-1][j]
- 等于从前i-1个物品中选，背包容量为j时的最大价值
选第i个物品
- 前提条件：背包容量j大于等于第i个物品的重量才能选if(j>=w[i])
- 等于f[i][j]=v[i]+f[i-1][j-w[i]]
- 等于第i个物品的价值加上从前i-1个物品中选，背包容量为（j减去第i个物品的重量）时的最大价值
当选第i个物品时，要考虑选第i个物品和不选第i个物品两种情况的较大值作为f[i][j]的最优解
- 等于f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])
- 等于不选第i个物品和选第i个物品两者的较大值

#include <stdio.h>
#define N 4 //物品数量
#define W 5 //背包容量

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int i, j;
    int v[] = {0, 2, 4, 5, 6};//物品价值数组
    int w[] = {0, 1, 2, 3, 4};//物品重量数组
    int f[N + 1][W + 1] = {};//子问题解数组
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= W; j++) {
            f[i][j]=f[i-1][j];//默认不选第i个物品
            if(j>=w[i]){//选第i个物品的前提条件
                f[i][j]=max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
            }
            /*if (j >= w[i]) {//选第i个物品
                //不选第i个物品 和 选第i个物品 两者的较大值
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
            } else {//不选第i个物品
                //从前i-1个物品中选，背包容量为j时的最大价值
                f[i][j] = f[i - 1][j];
            }*/
        }
    }
    printf("%d\n", f[N][W]);
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= W; j++) {
            printf("%d", f[i][j]);
        }
        printf("\n");
    }
    return 0;
}

矩阵连乘

时间复杂度为O(n^3)，空间复杂度为O(n^2)

两个矩阵A(_{m*n}) 和 B(_{n*p}) 相乘的次数为：m*n*p
相乘之后得到新的矩阵为：(A*B)_{(m*p)}

例如：A1_{(3*4)} 和A2_{(4*5)} 相乘的次数为：3*4*5
相乘之后得到新的矩阵为：(A1*A2)_{(3*5)}

最长公共子序列的时间复杂度为O(n^2)

8.5 贪心法

可以用贪心法求得最优解的问题中看到，这类问题一般具有两个重要的性质：

最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。

如果题目提到归并排序，则时间复杂度的O(nlgn)
一般部分背包的时间复杂度O(nlgn)

部分背包问题

#include <stdio.h>
#define N 5 // 物品数量
#define W 10 // 背包容量

int v_temp[N + 1], w_temp[N + 1]; // 物品价值数组 和 物品重量数组的临时数组
double vw_temp[N + 1]; // 物品单位重量价值数组的临时数组
double answer[N + 1]; // 解方案数组

// 归并排序
void merge_sort(int v[], int w[], double vw[], int l, int r) {
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(v, w, vw, l, mid), merge_sort(v, w, vw, mid + 1, r);

    int i = l, j = mid + 1, k = 1;
    while (i <= mid && j <= r)
    {
        if (vw[i] >= vw[j]) { // 按照 物品单位重量价值数组 从大到小的顺序排序
            vw_temp[k] = vw[i];
            v_temp[k] = v[i];
            w_temp[k] = w[i];

            k ++ , i ++ ;
        } else {
            vw_temp[k] = vw[j];
            v_temp[k] = v[j];
            w_temp[k] = w[j];

            k ++ , j ++ ;
        }
    }

    while (i <= mid) {
        vw_temp[k] = vw[i];
        v_temp[k] = v[i];
        w_temp[k] = w[i];

        k ++ , i ++ ;
    }

    while (j <= r) {
        vw_temp[k] = vw[j];
        v_temp[k] = v[j];
        w_temp[k] = w[j];
        k ++ , j ++ ;
    }

    for (i = l, j = 1; i <= r; i ++ , j ++ ) {
        vw[i] = vw_temp[j];
        v[i] = v_temp[j];
        w[i] = w_temp[j];
    }
}

// 显示物品价值、重量、单位重量价值数组
void show(int v[], int w[], double vw[]) {
    int i;
    printf("物品价值数组：");
    for (i =  1; i <= N; i ++ ) printf("%d ", v[i]);
    printf("\n");

    printf("物品重量数组：");
    for (i =  1; i <= N; i ++ ) printf("%d ", w[i]);
    printf("\n");

    printf("物品单位重量价值数组：");
    for (i =  1; i <= N; i ++ ) printf("%.1lf ", vw[i]);
    printf("\n");
}

// 求解部分背包问题最优解
double Max_Value(int v[], int w[], double vw[]) {
    double result = 0.0;
    int i;
    int W_temp = W;
    for (i = 1; i <= N; i ++ ) {
        if (W_temp >= w[i]) { // 当前背包容量 大于等于 物品重量 就直接全部装入到背包中
            answer[i] = 1.0;

            result = result + v[i];

            W_temp = W_temp - w[i];
        } else { // 当前背包容量 小于 物品重量 就应该将该物品的一部分装入到背包中
            break;
        }
    }

    if (W_temp > 0 && i <= N) { // 当前背包还有剩余容量 并且 还有可选的物品
        answer[i] = (double) W_temp / w[i];

        result = result + W_temp * vw[i];
        // result = result + (double) W_temp / w[i] * v[i];
    }

    return result;
}

int main() {
    int v[] = {0, 6, 3, 5, 4, 6}; // 物品价值数组
    int w[] = {0, 2, 2, 6, 5, 4}; // 物品重量数组
    double vw[N + 1]; // 物品单位重量价值数组
    int i;
    // 初始化 物品单位重量价值数组
    for (i = 1; i <= N; i ++ ) vw[i] = (double) v[i] / w[i];
    printf("排序前：\n");
    show(v, w, vw);

    merge_sort(v, w, vw, 1, N);

    printf("排序后：\n");
    show(v, w, vw);

    double result = Max_Value(v, w, vw);
    printf("\nresult = %.2lf\n", result);
    printf("\n");
    
    printf("解方案结果：");
    for (i = 1; i <= N; i ++ ) printf("%.1lf ", answer[i]);
    return 0;
}

8.6 回溯法

回溯法是一个既带有系统性又带有跳跃性的搜索算法，它在包含问题的所有解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

n皇后问题

给定一个N x N的棋盘，要在棋盘上摆放 N 个皇后，并且满足 N 个皇后中任意两个皇后都不处于同一行、同一列、同一斜线上（正斜线、反斜线）
判断同一列：Qi列==Qj行
判断同一斜线：|Qi行-Qj行|==|Qi列-Qj列|

代码实现（非递归）：

//
// Created by XFanny on 2024/4/28.
//
#include<stdio.h>
#include<math.h>
#include <stdlib.h>

#define N 4 //定义有多少个皇后

int q[N + 1]; //存储皇后的列号
//说明：对应q下标表示第几行，即第几个皇后，q[i]=val,val表示第i+1个皇后，放在第i+1行的value+1列
//放置第j个皇后位置，检查第j个皇后的位置是否合法
int check(int j) {
    int i;
    for (i = 1; i < j; i++) {
        // 说明
        // 1. q[i] == q[j] 表示判断第j个皇后是否和i-1个皇后在同一列
        // 2.  abs(i - j) == abs(q[i] - q[j]) 表示判断第j个皇后和第i个皇后在同一斜线
        // 判断是否在同一列和同一斜线
        if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) {
            return 0;
        }
    }
    return 1;
}

//求解N皇后的方案
void queen() {
    int i;
    //初始化皇后的列号数组q为0，表示还没有开始摆放皇后
    for (i = 0; i <= N; i++) {
        q[i] = 0;
    }
    int answer = 0; //方案数
    int j = 1;//表示正在摆放第j个皇后，初始化为1
    while (j >= 1) {
        q[j] = q[j] + 1;//棋盘从0列开始，让第j个皇后向后一列摆放到第1列

        while (q[j] <= N && !check(j)) {//判断第j个皇后的位置是否合法，是否与之前的皇后位置冲突
            //不冲突，接着放n+1个皇后，即开始递归
            q[j] = q[j] + 1;
        }

        if (q[j] <= N) { //表示第j个皇后找到一个合法的摆放位置
            if (j == N) { //找到了N皇后的一组解
                answer = answer + 1;
                printf("方案%d:", answer);
                for (i = 1; i <= N; i++) {
                    printf(" %d ", q[i]);
                }
                printf("\n");
            } else {
                //继续摆放下一个皇后，走下一列
                j = j + 1;
            }
        } else {
            //表示第j个皇后找不到一个合法的摆放位置
            q[j] = 0; //还原第j个皇后的位置
            j = j - 1; //回溯
        }
    }
}
int main() {
    queen();
    return 0;
}

递归代码实现：

//
// Created by XFanny on 2024/5/6.
//
#include<stdio.h>
#include<math.h>
#include <stdlib.h>

#define N 4 //定义有多少个皇后

int q[N + 1]; //存储皇后的列号
//说明：对应q下标表示第几行，即第几个皇后，q[i]=val,val表示第i+1个皇后，放在第i+1行的value+1列
//放置第j个皇后位置，检查第j个皇后的位置是否合法
int answer;

int check(int j) {
    int i;
    for (i = 1; i < j; i++) {
        // 说明
        // 1. q[i] == q[j] 表示判断第j个皇后是否和i-1个皇后在同一列
        // 2.  abs(i - j) == abs(q[i] - q[j]) 表示判断第j个皇后和第i个皇后在同一斜线
        // 判断是否在同一列和同一斜线
        if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) {
            return 0;
        }
    }
    return 1;
}

//递归求解n皇后
void queen(int j) {
    int i;
    for (i = 1; i <= N; i++) {
        q[j] = i;
        if (check(j)) { //当摆放的皇后位置合法时
            if (j == N) { //找到了N皇后的一组解
                answer = answer + 1;
                printf("方案%d: ", answer);
                for (i = 1; i <= N; i++) {
                    printf("%d ", q[i]);
                }
                printf("\n");
            } else {
                queen(j + 1);
            }
        }
    }
}

int main() {
    queen(1);
    return 0;
}

8.7 分支限界法

分支限界法与回溯法的求解目标不同。
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法以广度优先或以最小耗费优先的方式搜索解空间树T。

结语

这份笔记由我在备考软件设计师中级考试的过程中编写，包含了我对知识点的理解与总结。如果您觉得这份笔记对您有帮助，并希望分享给更多的人，我十分乐意。但请在转载时务必注明出处，以尊重作者的劳动成果，感谢您的理解与支持。

在此特别强调，本人编写笔记的所需部分资源均源于网络公开资源，旨在为大家提供一个学习和交流的内容，未经原作者授权，如若不慎侵犯您的合法权益，请您立即通过有效联系方式通知我，并附上相关证明材料。一旦核实无误，我将在第一时间删除涉事资源，全力保障您的合法权利不受损害。

每篇一句：“不应该在该奋斗的年纪去选择偷懒，只有度过了一段连自己都被感动了的日子，才会变成那个最好的自己。”
如果觉得对您有用，请点个赞或者收藏鼓励我持续更新吧！
恭喜您，已挑战成功第八关，请前往第九关进行挑战吧【整理中……】

原文地址：https://blog.csdn.net/XFanny/article/details/143076901

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux中安装tesserocr遇到的那些坑
下一篇：操作系统：进程通信实践-用管道实现进程之间的通信（详解）

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

2024年软件设计师中级（软考中级）详细笔记【8】算法设计与分析（分值4~5）

目录

前言

第8章 算法设计与分析（4~5分）

8.1 算法设计与分析的基本概念

8.1.1 算法

8.2 算法分析继承

8.2.0 大O表示法

8.2.1 时间复杂度

8.2.2 递归式时间复杂度

8.2.3 空间复杂度

8.2.4 渐进符号

8.2.5 递归式

8.2.5.1 展开法域代换法

8.2.5.2 递归式主方法

8.3 分治法

8.4 动态规划法

0-1 背包问题

矩阵连乘

8.5 贪心法

8.6 回溯法

n皇后问题

8.7 分支限界法

结语

相关文章

第8章算法设计与分析（4~5分）