算法分析与设计整理(自用)

算法分析与设计整理(自用),第1张

分治法 二分查找
/**
* a[]:搜索的数组
* x:所要搜索的数值
* n:数组长度
* */
int BinarySearch(int a[], int x, int n){
    int left  =0;
    int right = n-1;
    while(left <= right){
        int middle = (left - right)/2;
        if(x == a[middle]) return middle;
        if(x > a[middle]) left = middle + 1;
        else right = middle-1;
    }
    return -1;
}
归并排序
void mergeSort(int[] arr,int low,int high,int[] tmp){
	if(low<high){
		int mid = (low+high)/2;
		mergeSort(arr,low,mid,tmp); 	//对左边序列进行归并排序
		mergeSort(arr,mid+1,high,tmp);  //对右边序列进行归并排序
		merge(arr,low,mid,high,tmp);    //合并两个有序序列
	}
}
void merge(int[] arr,int low,int mid,int high,int[] tmp){
    int i = 0;
    int j = low, k = mid+1;  //左边序列和右边序列起始索引
    while(j <= mid && k <= high){
        if(arr[j] < arr[k]){
            tmp[i++] = arr[j++];
        }else{
            tmp[i++] = arr[k++];
        }
    }
    //若左边序列还有剩余,则将其全部拷贝进tmp[]中
    while(j <= mid){
        tmp[i++] = arr[j++];
    }

    while(k <= high){
        tmp[i++] = arr[k++];
    }

    for(int t=0;t<i;t++){
        arr[low+t] = tmp[t];
    }
}
快速排序
void function(int[] arr, int low, int high){
    if(low>high){
        return;
    }
    int i = low;
    int j = high;
    int temp = arr[low];
    while (i<j){
//      while (arr[high]
//      while (arr[low]>arr[i]) i++;
        while (temp<arr[j] && i<j) j--;
        while (temp>arr[i] && i<j) i++;
//      if (arr[i]>arr[j]){
        if(i<j){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[low] = arr[j];
    arr[j] = temp;
    function(arr, low, j);
    function(arr, j+1,high);
}
动态规划 矩阵连乘问题
void function(int[] p){
    int n = p.length+1;
    int[][] dp = new int[n+1][n+1];
    int[][] breakPoints = new int[n+1][n+1];
    for(int i=0;i<n;i++) dp[i][i]=0;
    for(int r=2;r<n;r++){
//      for(int i=0;i
        for(int i=1;i<n-r;i++){
            int j = i+r-1;
//          dp[i][j] = dp[i][i]+dp[i][j]+dp[i][i+1]*dp[i+1][j]*dp[i][j];
            dp[i][j] = dp[i+1][j]+p[i-1]*p[i]*p[j];
            breakPoints[i][j] = i;
            for(int k=i;k<n;k++){
//              int t = dp[i][k]+dp[k][j]+dp[i][k]*dp[k][j]*dp[i][j];
                int t = dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
                if (t<dp[i][j]) dp[i][j]=t;
                breakPoints[i][j] = k;
            }
        }
    }
}
01背包问题
/**
 * val[] 物品价值
 * w[] 物品重量
 * m 背包的容量
 * n 物品的数量
 * */
void function(int[] val, int[] w, int m, int n){
    // dp[i][j] 表示在前i个物品中能够装入容量为j的背包中最大价值
    int[][] dp = new int[n+1][m+1];
    for (int i = 1; i < n+1; i++) {
        for (int j = 0; j < m+1; j++) {
            //根据公式,当新增的商品重量大于当前背包的容量时,采取上一次的装入策略
            if (w[i-1] > j) dp[i][j] = dp[i-1][j];
            //当新增重量等于或者或者小于背包容量时,判断剩余容量的最佳策略+当前容量的最佳策略,与上次策略哪个大,取大的。
            else dp[i][j] = Math.max(dp[i-1][j],val[i-1] + dp[i-1][j - w[i-1]]);
        }
    }
}
最长公共子序列问题
int function(String A, int n, String B, int m) {
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}
最优二叉搜索树问题(没看懂。。) 最优三角剖分
void function(int[][] metrics) {
    int n = metrics.length+1;
    int[][] dp = new int[n][n];//存放解
    for (int i = 0; i < n; i++)//初始化
        dp[i][i] = 0;
    //r为间隔边数,先从两条边开始,即三个点组成的凸多边形(三角形)
    for (int r = 2; r < n; r++) {
        for (int i = 1; i < n - r; i++) { //i初始边
            //i的范围 (n-1-1)-(i-1)>=r → i
            int j = i+r-1;//j为i加上间隔边数
            //metrics[i-1][i]+metrics[i][j]+metrics[i-1][j]: 求三角形权重
            dp[i][j] = dp[i][i] + dp[i+1][j] + metrics[i-1][i]+ metrics[i][j]+ metrics[i-1][j];
            //当边的取值是从i到j时的最优解 是i到i时最优解和i+1到j时的最优解再加三角形的权值
            //开始考虑不同的k值
            for (int k = i + 1; k < j; k++) {
                int min = dp[i][k] + dp[k+1][j] + metrics[i-1][k]+ metrics[k][j]+ metrics[i-1][j];
                //metrics[i-1][k]+metrics[k][j]+metrics[i-1][j]: 求三角形权重
                if (min < dp[i][j]) {//有更优解
                    dp[i][j] = min;
                }
            }
        }
    }
}
贪心算法 最优装载问题
//c 载重量
//w 每个集装箱重量
int function(int[] w, int c){
    Arrays.sort(w);
    int result = 0;
    for(int i=0;i<w.length;i++){
        if(result+w[i] <= c) result += w[i];
        else break;
    }
    return result;
}
背包问题
//n 物品的个数
//C 背包容量
//weights[] 物品重量
//values[] 物品价值
//putin[] 用来记录第i个物品是否装入背包
double function(double[] weights, double[] values, double[] putin, double C, int n){
    sort(weights, values,n); //以物品的 价值/重量 为基准,对物品价值、重量这两个数组进行排序
    int i;
    double total = 0;
    for (i = 0; i < n; i++) {
        if (weights[i] <= C){//如果背包剩余的容量大于等于第i个物体的重量
            putin[i] = 1;   //把第i个物体整个装进背包
            C = C - weights[i];  //背包的剩余容量减少了第i个物体的重量
        }else {
            break;  //退出循环
        }
    }
    if (i < n){//判断是否第n个物体整个装进去背包里了,如果i<=n表示否定
        putin[i] = C/ weights[i];//背包剩余容量/第i个物品的重量(第i个物品放进去了一部分)
    }
    for(i = 0; i < n; i++){
        total = total+ putin[i]* values[i];//计算总价值
    }
    return total;
}
单源最短路径问题
//matrix距离标记矩阵,没有直接联通的两个点距离用MAX_VALUE或所有距离之和
void dijkstra(int[][] matrix, int source) {
    //最短路径长度
    int[] shortest = new int[matrix.length];
    //判断该点的最短路径是否求出
    int[] visited = new int[matrix.length];
    //存储输出路径
    String[] path = new String[matrix.length];
    //初始化输出路径
    for (int i = 0; i < matrix.length; i++) {
        path[i] = (source+1) + "->" + (i+1);
    }
    //初始化源节点
    shortest[source] = 0;
    visited[source] = 1;
    for (int i = 1; i < matrix.length; i++) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int j = 0; j < matrix.length; j++) {
            //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
            if (visited[j] == 0 && matrix[source][j] < min) {
                min = matrix[source][j];
                index = j;
            }
        }
        //更新最短路径
        shortest[index] = min;
        visited[index] = 1;
        //更新从index跳到其它节点的较短路径
        for (int m = 0; m < matrix.length; m++) {
            if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
                matrix[source][m] = matrix[source][index] + matrix[index][m];
                path[m] = path[index] + "->" + (m+1);
            }
        }
    }
    //打印最短路径
    for (int i = 0; i < matrix.length; i++) {
        if (i != source) {
            String result;
            if (shortest[i] == Integer.MAX_VALUE) {
                result = (source+1) + "到" + (i+1) + "不可达";
            } else {
                result = (source+1) + "到" + (i+1) + "的最短路径为:" + path[i] + ",最短距离是:" + shortest[i];
            }
            System.out.println(result);
        }
    }
}
回溯算法 n皇后问题
/**
 * M:用于标记皇后放不放的矩阵
 * x:目前在判断第x个皇后房放和不放
 * num:一共有几种解法
 * */
void dfs(int[] M, int x){
    if(x==M.length){
        num++;//如果最后一个空位已经被占满了, 那就表示找到了一种安全状态, 那计数器就可以+1
        return;
    }
    for(int y=1;y<M.length;y++){
        if (isSafety(M, x, y)) {//用于判断处在xy位置的王后是否是安全的(是否和之前已经存在的几个王后冲突)
            M[x] = y;       //只要判断如果王后在这个点上是安全的 那就可以放上了
            dfs(M,x+1);  //寻找当x=x+1的时候, 王后放的位置安全的状态, 递归
        }
    }
    M[x] = 0;//如果能运行到这一步, 说明前面判定M已经满了, 开始进行回溯(如何保证第二次寻找安全状态不会和第一次一样?)
    //这一步最好不要省, 因为在下面的判断当中, 为遍历的置为0有利于提高效率
}
旅行售货员问题
/**
 * int cityCount    城市数量
 * int minVal       最小的值
 * int[] minArr     最小的集合
 * int minValTemp   临时 最小的值
 * int[] chooseCity 临时 最小集合
 * int[] chooseCity 记录是否走过这个城市
 * int[][] Metrics  城市之间的距离
 * */
void travel(int step){
    if(step >= cityCount){//表示走完了所有城市
        if(minValTemp < minVal){
            minArr = Arrays.copyOf(minArrTemp,4);
            minVal = minValTemp;
        }
        return;
    }
    for(int i = 0; i < cityCount ; i++){
        //下一步没有走过,并且可达,则选中
        if(chooseCity[i] == 0 && Metrics[minArrTemp[step-1]][i] != -1){
            minArrTemp[step] = i;
            minValTemp += Metrics[minArrTemp[step-1]][i];
            chooseCity[i] = 1;
            travel(step+1);
            //还原现场
            minArrTemp[step] = -1;
            chooseCity[i] = 0;
            minValTemp -= Metrics[minArrTemp[step-1]][i];
        }
    }
}
01背包问题
/**
 * Item[] items; // 封装的物品
 * float weight; // 背包容量
 * float nowWeight = 0; // 记录当前以拿重量
 * float nowPrice = 0; // 记录当前以拿价格
 * float betterValue; // 记录最多的价格
* */
void traceBack(int t) {//t指的是 第t个物品
    if (t >= items.length) {//当所有物品全都遍历完成的时候
        betterValue = nowPrice;// 记录最多的价格
        output(items);// 输出最多的价格
        return;
    }
    // 首先判断第t个物品如果拿了会怎样
    if (nowWeight + items[t].w < weight) {//首先需要重量加起来不超重
        nowWeight += items[t].w;
        nowPrice += items[t].v;
        items[t].take = true;
        traceBack(t + 1);//递归判断下一个t
        // 还原现场
        nowWeight -= items[t].w;
        nowPrice -= items[t].v;
        items[t].take = false;
    }
    // 推出回溯并还原现场,判断第t个物品如果不拿会怎样
    // bound(int i) 用于计算右面的所有item如果把 量/重 从大到小放到背包中能得到的价值
    if (bound(t + 1) > betterValue) {//注意这里是和betterValue比
        traceBack(t + 1);
    }
}
分支限界法 01背包问题 单源最短路径问题 旅行售货员问题 算法复杂度 几种经典问题的算法复杂度

二分查找:O(nlogn)

归并排序:O(nlogn)

快速排序:O(nlogn)

矩阵连乘:时间复杂度O(n^2) 空间复杂度O(n^3)

最优三角剖分:时间复杂度O(n^2) 空间复杂度O(n^3)

最长公共子序列(LCS):O(mn)

Dijkstra:O(n^2)

01背包问题:O(n2^n) 或 O(nc)

哈夫曼树:O(nlg(n))

渐进阶从低到高:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/1498204.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-25
下一篇 2022-06-25

随机推荐

  • 百易是哪个国家的品牌?

    【导读】:BOVOEE百易BOVOEE诞生于德国,她传承了德国千年文明。集严谨﹑品质﹑艺术于一身,显尽纯美巅峰之品位。百易是中国品牌。BOVOEE百易BOVOEE诞生于德国,她传承了德国千年文明。集严

    2022-08-19
    0 0 0
  • VSGO品牌的中文名是什么?

    【导读】:VSGO的中文名是威高,威高是中国的品牌。始建于1988年,知名医疗器械品牌,以一次性医疗器械和药业为主的医疗系统解决方案供应商威高集团有限公司始建于1988年,以一次性医疗器械和药业为主业

    2022-08-19
    0 0 0
  • ELLE内衣是哪个国家的品牌?

    【导读】:  柏毅制衣(广州)有限公司隶属于宝佳集团,是内衣业最资深的知名厂家之一,服务于众多国际品牌,例如:Jocky, ZARA, H&M 等。宝佳集团在北京,泰国...ELLE内衣是中国品牌。 

    2022-08-19
    0 0 0
  • IMEDEEN品牌的中文名是什么?

    【导读】:IMEDEEN的中文名是怡美缇,怡美缇是中国的品牌。1980,一位瑞士生化博士在“减龄医学”研究中,发现了可以深层修护全身肌肤的口服配方,其中含有一种有效延缓肌肤衰老的深海鱼类蛋白精华Bio

  • 山鹰纸业是哪个国家的品牌?

    【导读】:山鹰纸业始于1957年,其工业造纸及包装印刷拥有较大规模,集再生纤维、造纸、包装、印刷、贸易、物流、投融资等为一体的高新技术企业山鹰纸业是中国品牌。山鹰纸业始于1957年,其工业造纸及包装印

    2022-08-19
    0 0 0
  • 金健电器是哪个国家的品牌?

    【导读】:金健电器金健电器品牌隶属于阳江市江城区华科智音音响器材有限公司,成立于2014年,公司主要生产经营影音用品,其产品种类齐全,性价比高,公司秉承“...金健电器是中国品牌。金健电器金健电器品牌

    2022-08-19
    0 0 0
  • 吉林联通是哪个国家的品牌?

    【导读】:吉林联通吉林联通品牌隶属于中国联合网络通信有限公司吉林省分公司,公司拥有覆盖全省、结构合理、技术先进、功能强大的现代通信网络,主要经营移动通...吉林联通是中国品牌。吉林联通吉林联通品牌隶属

    2022-08-19
    0 0 0
  • 铂尔迅是哪个国家的品牌?

    【导读】:铂尔迅PORSON“PORSON铂尔迅”系厦门泊尔迅贸易有限公司旗下平台品牌,诞生于2011年4月,自创始以来,旨在打造中国餐厨用具最具性价比的系列产品。“P...铂尔迅是中国品牌。铂尔迅P

    2022-08-19
    0 0 0
  • 树森是哪个国家的品牌?

    【导读】:树森树森品牌隶属于象山安康乐保健寝具工艺厂,创立于2001年。本公司位于浙江省。主营冰晶凉垫、水席、凉席、古藤席等。公司秉承“保证一流质量,保持...树森是中国品牌。树森树森品牌隶属于象山安

    2022-08-19
    0 0 0

发表评论

登录后才能评论

评论列表(0条)

保存