深入浅出的算法设计与分析技巧解读(软件设计师笔记)

发布时间:2023年12月18日

😀前言
在计算机科学的庞大体系中,算法始终占据着核心的地位,充当着解决问题的“钥匙”。本章主要深入探讨了算法设计与分析这一主题,旨在通过具体的问题解析和代码实现,引导读者深入理解各种经典算法的设计原理和应用策略。我们将探讨如何量化算法的效率和效果,并通过多种算法策略(如回溯法、分治法、动态规划法和贪心法)的探讨,展示了算法如何在不同的问题领域中发挥其关键作用。
本章的核心不仅是在于算法本身的分析和实现,更在于培养读者独立分析问题、选择或设计算法的能力。我们将通过多个问题实例,展示了如何通过不同算法策略,从不同的角度分析和解决问题。

🏠个人主页:尘觉主页
在这里插入图片描述

🧑个人简介:大家好,我是尘觉,希望我的文章可以帮助到大家,您的满意是我的动力😉😉

在csdn获奖荣誉: 🏆csdn城市之星2名
???? ???? ???? ???? ???? ???? ???? ???? 💓Java全栈群星计划top前5
???? ???? ???? ???? ???? ???? ???? ???? 🤗 端午大礼包获得者
???? ???? ???? ???? ???? ???? ???? ???? 🥰阿里云专家博主
???? ???? ???? ???? ???? ???? ???? ???? 😉亚马逊DyamoDB结营

💕欢迎大家:这里是CSDN,我总结知识的地方,欢迎来到我的博客,感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦😊

第八章 算法设计与分析

时间复杂度

算法时间复杂度以算法中基本操作重复执行的次数(简称为频度)作为算法的时间度量。一般不必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级即可,如O(1)、O(㏒?n)、O(n)或O(n2)等。


递归式时间复杂度:递归的次数 x 每次递归的时间复杂度

主方法。主方法也称为主定理,给出了求解以下形式的递归式的快速方法。

空间复杂度

非递归:O(1) O(n) O(n2)

回溯法
n皇后问题

#include<stdio.h>
#include"stdlib.h"

int Place(int *Column,int index){
    int i;
    for(i=1;i<index;i++){
        int Column_differ = abs(Column[index] - Column[i]);
        int Row_differ = abs(index - i);
        if(Column[i] == Column[index] || Column_differ == Row_differ)
            return 0;
    }
    return 1;
}

void N_Queue(int n){
    int Column_Num[n+1];
    int index = 1;
    int i;

    int answer_num = 0;
    for(i=1;i<=n;i++)
        Column_Num[i] = 0;
    while(index>0){
        Column_Num[index]++;
        while(Column_Num[index] <= n && !Place(Column_Num,index))
            Column_Num[index]++;
        if(Column_Num[index] <=n){
            if (index == n) {
                answer_num++;
            
                printf("方案%d:",answer_num);

                for(i=1;i<= n;i++){
                    printf("%d ",Column_Num[i]);
                }
                printf("\n");
            }else {
                index++;
                Column_Num[index]=0; 
            }
        }else {
            index--;
        }
    }
}

int main(){
    N_Queue(6);
    return 0;
}
分治法

递归有两个基本要素:

  • 边界条件,即确定递归到何时终止,也称为递归出口
  • 递归模式,即大问题是如何分解为小问题的,也称为递归体

分支算法在每一层递归上都有 3 个步骤:

  1. 分解。将原问题分解成一系列子问题。
  2. 求解。递归地求解各子问题。若子问题足够小,则直接求解。
  3. 合并。将子问题的解合并成原问题的解。
归并排序算法
#include<stdio.h>

#define INT_MAX 2147483647
/**
 * 归并排序
**/
void Merge(int A[],int p,int q,int r){
    int n1 = q - p + 1,n2 = r -q,i,j,k;
    int L[50],R[50];
    for(i=0;i<n1;i++)
        L[i] = A[p+i];
    for(j=0;j<n2;j++)
        R[j] = A[q+j+1];
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i=0;
    j=0;
    for(k=p;k<r+1;k++){
        if(L[i] < R[j]){
            A[k] = L[i];
            i++;
        }else{
            A[k]=R[j];
            j++;
        }
    }
}

void MergeSort(int A[],int p,int r){
    int q;
    if(p < r){
        q = (p+r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q+1, r);
        Merge(A, p, q,r);
    }
}



int main(){
    int A[] = {4,1,3,6,7,5,2,9};
    MergeSort(A, 0, 7);

    int i;
    for (i = 0; i<8; i++) {
        printf("%d ",A[i]);
    }
    printf("\n");
    return 0;
}

最大字段和问题

#include<stdio.h>
#include<stdlib.h>

int MaxSubSum(int * Array,int left,int right){
    int sum = 0;
    int i;
    if(left == right){ /*分解到单个整数,不可继续分解*/
        if(Array[left] > 0)
            sum = Array[left];
        else
            sum = 0;
    }else{
        /*从 left 和 right 的中间分解数组*/
        int center = (left + right)/2; /*划分的位置*/
        int leftsum = MaxSubSum(Array, left, center);
        int rightsum = MaxSubSum(Array, center+1, right);
        /*计算包括 center 的最大值,判断是情形1、情形2还是情形3*/
        int s1 = 0;
        int lefts = 0;
        for(i = center;i >= left;i--){
            lefts = lefts + Array[i];
            if(lefts > s1)
                s1 = lefts;
        }
        int s2 = 0;
        int rights = 0;
        for(i = center + 1;i<= right;i++){
            rights = rights + Array[i];
            if(rights > s2)
                s2 = rights;
        }
        sum = s1 + s2;

        /*情形1*/
        if (sum < leftsum) {
            sum = leftsum;
        }
        /*情形2*/
        if(sum < rightsum){
            sum = rightsum;
        }
    }
         return sum;
}

int main(){
    int *Array = (int *)malloc(6*sizeof(int));
    Array[0] = -2;
    Array[1] = 11;
    Array[2] = -4;
    Array[3] = 13;
    Array[4] = -5;
    Array[5] = -2;

    int result = MaxSubSum(Array, 0, 5);
    printf("%d\n",result);

    return 0;
}

动态规划法
0-1 背包问题
#include<stdio.h>

#define N 4 // 物品数量
#define W 5 // 背包容量

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

int main(){
    int v[] = {0,2,4,5,6}; // 物品价值数组
    int w[] = {0,1,2,3,4}; // 物品重量数组

    int f[N + 1][W + 1] = {}; // 子问题解数组

    int i,j;
    for(i=1;i<=N;i++){
        for(j=1;j<=W;j++){
            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 个物品
                f[i][j] = f[i - 1][j]; // 等于从前 i-1 个物品中选,背包容量为 j 时的最大价值    
            }
        }
    }

    printf("%d\n",f[N][W]);

    return 0;
}

时间复杂度:O(N*W) N:物品数量 W:背包容量

矩阵连乘问题
  • 时间复杂度:O(n3)
  • 空间复杂度O(n2)
贪心法
部分背包问题
#include<stdio.h>

#define N 5     // 物品数量
#define W 100   // 背包容量

// 显示物品价值、重量、单位重量价值数组
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("%0.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]){
            result = result + v[i];

            w_temp = w_temp - w[i];
        }else{
            break;
        }
    }

    if(w_temp > 0 && i<=N){
        result = result + w_temp * vw[i];
    }
    return result;
}

int main(){

    int v[] = {0,65,20,30,60,40};   // 物品价值数组
    int w[] = {0,30,10,20,50,40};   // 物品重量数组

    double vw[N + 1]; // 物品单位重量价值数组

    int i;
    // 初始化 物品单位重量价值数组
    for(i = 1;i<=N;i++) vw[i] = (double) v[i] / w[i];

    show(v, w, vw);

    double result =Max_Value(v, w, vw);
    printf("\nreslut %.1lf\n",result);

    return 0;
}

😄总结

经过对算法设计与分析的深入探讨,我们对各类算法及其在不同问题场景中的应用有了更加深入的理解。
本章囊括了从基本的时间、空间复杂度分析,到复杂的递归、动态规划和贪心算法的设计与应用。我们通过代码示例,深入浅出的探讨了每种算法的优缺点和适用场景,希望能够为读者在未来的学习和工作中解决实际问题提供指导。

在今后的实际应用中,算法的选择和设计不应僵化地依赖于理论和模型,而应充分考虑实际问题的特性,发挥创新和批判性思维,不断拓宽问题解决的多元路径。我们期待读者在理解和掌握了本章内容的基础上,能够在未来的学习和研究中,更加灵活和深刻地应用算法,解决更加复杂和多元的问题。

在算法的世界里,每一个问题都有它的解决之道。而找到最优、最适应的解决方案,需要我们不断的学习和实践。希望本章内容能为我们的算法学习之旅打下坚实的基础,使我们在解决问题的道路上更加从容和自信。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

文章来源:https://blog.csdn.net/apple_67445472/article/details/133529304
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。