首页 > 编程语言 >算法-分治和逆序

算法-分治和逆序

时间:2024-09-20 11:51:32浏览次数:10  
标签:count int 分治 length ++ 算法 序列 逆序

分治法(Divide and Conquer)是一种重要的算法设计范式,它通过将复杂的问题分解成更小、更易于管理和解决的子问题,然后递归地解决这些子问题,最后将子问题的解合并以得到原问题的解。分治法通常用于排序、搜索、数学计算和优化等问题。

分治法的核心思想可以概括为三个步骤:

  1. 分解(Divide):将原问题分解为若干个规模较小的相同问题。

  2. 解决(Conquer):递归地解决这些子问题。如果子问题足够小,可以直接解决。

  3. 合并(Combine):将子问题的解合并以得到原问题的解。

时间复杂度
  1. 最佳情况:如果每次分区操作都能将数组均匀地分成两个相等的部分,那么快速排序的时间复杂度是最优的。在这种情况下,递归的深度是 logn(其中 n 是数组的长度),每一层的工作时间是 O(n)。因此,总的时间复杂度是 �(�log⁡�)O(nlogn)。

  2. 平均情况:在大多数情况下,快速排序的性能接近最佳情况,尽管可能不是完全均匀的划分。平均情况下的时间复杂度也是 O(nlogn)。

  3. 最坏情况:如果每次分区操作都极不均匀,例如每次只将数组分成一个元素和其余元素两部分,那么递归的深度将是 �n,每一层的工作时间仍然是 �(�)O(n),但总共有 �n 层。因此,总的时间复杂度是 O(n的平方)。这种情况通常发生在数组已经有序或者完全逆序的情况下。

逆序

2 4 1 3 5

初始化逆序数 count=0;

(2,4)正序

(2,1)逆序,count=1;

(2,3)正序

(2,5)正序

(4,1)逆序,count=2;

(4,3)逆序,count=3;

(1,3)正序

(1,5)正序

(3,5)正序

一般来讲一个一个对照的话,一般就是也就是说这种算法的时间复杂度上限为O(n2)。

但是分治策略,可以降低到nlogn 因此可以直接操作。

对应算法

两个有序的序列 去合并成新序列,并且找到逆序数。

假定分解后的两个序列分别为A,B,(A在前,B在后)已得到A,B的逆序数分别为rA,rB且假定计数完逆序数后把A,B排序为有序序列,以此为基础,得到A,B两序列元素之间的逆序数的合并算法为MAC算法(有(ai,bj)组合,ai来自A,bj来自B,如果有逆序就要计数)。

算法 MAC. 给定两个有序序列A、B,输出它们之间的逆序数和一个合并后有序 的序列C。

MAC1. [初始化变量] 初始化A、B、C的下标i=0,j=0,k=0,和计数值               count=0,初始化C为空序列;

MAC2. [A或B是否没有元素?]if A没有元素 or B没有元素,把有元素 不空的那个序列剩余的元素全部加到C的后面并返回count和C;

MAC3. [是否要增加逆序数?] If A[i]>B[j],count增加的计数值为A中还              有的元素数量,把B[j]从B中移到C的最后面,j←j+1,k←k+1;

MAC4. [无需增加逆序数] 把A[i]从A中移到C的最后面,                         i←i+1,k←k+1,回到MAC2。停止的条件就是有一方数组为空 停止全部操作加入到第三个序列
给个例子

例2.2 用MAC算法数一下序列A= {2,4 ,7},B={1,3,5,8}之间的逆序数。

初始化逆序数 i=0,j=0,k=0,count=0,C={};

A[i]>B[j],count=3,A={2,4,7},B={3,5,8},C={1},j=1,k=1;
A[i]<B[j],count=3,A={4,7},B={3,5,8},C={1,2},i=1,k=2;
A[i]>B[j],count=5,A={4,7},B={5,8}C={1,2,3},j=2,k=3;
A[i]<B[j],count=5,A={7},B={5,8}C={1,2,3,4},i=2,k=4;
A[i]>B[j],count=6,A={7},B={8}C={1,2,3,4,5},j=3,k=5;
A[i]<B[j],count=6,A={},B={8}C={1,2,3,4,5,7},i=3,k=6;
C={1,2,3,4,5,7,8},k=7,返回count,C;

最后计数值count=6,C={1,2,3,4,5,7,8}。

但我越来越感觉其实这个需要分治策略时候刚好是分成了两个有序数列。因为只有这样才是所谓mac算法的前提。这样不仅能够求出逆序数,同样的可以使得序列按照顺序排列。

SAC算法

递归算法和分治策略

将一个序列排序并且找到全部逆向序列数

算法 SAC. 给定序列S,输出该序列的的逆序数count和排序后的S

SAC1. [是否分解到基问题?] if S的元素只有1个,count=0,返回count              和S;

SAC2. [分解S]把S分解为两个序列A,B,A是前半,B是后半;

SAC3. [递归] 分别对A、B递归执行SAC算法,即(rA,A)=SAC(A);

              (rB,B)=SAC(B);

SAC4. [合并] 把对A,B执行MAC合并算法,即(r,S)=MAC(A,B);  SAC5. [加总] count←r+rA+rB,返回count,S。
java
package org.com.test;
import java.io.*;
import java.util.*;

public class SAC {
    public static void main(String[] args) {
        System.out.println("请输入待计数逆序的整数序列(以空格分开,各项值都不同)");
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        String[] tokens = line.split(" ");
        int[] S1 = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++) {
            S1[i] = Integer.parseInt(tokens[i]);
        }
        int count = sortAndCount(S1);
        for (int i = 0; i < S1.length; i++) {
            System.out.print(S1[i] + " ");
        }
        System.out.print("\n逆序计数为: " + count);
    }

    private static int sortAndCount(int[] S) {
        if (S.length == 1)
            return 0;
        int n = S.length / 2;
        int[] A = new int[n];
        int[] B = new int[S.length - n];
        int j = 0;
        for (int i = 0; i < A.length; i++)
            A[i] = S[j++];
        for (int i = 0; i < B.length; i++)
            B[i] = S[j++];
        int rA = sortAndCount(A);
        int rB = sortAndCount(B);
        int r = mergeAndCount(A, B, S);
        return (r + rA + rB);
    }

    private static int mergeAndCount(int[] A, int[] B, int[] C) {
        int i = 0, j = 0, k = 0, count = 0;
        for (int e: A)
            System.out.print(e);
        System.out.println();
        for (int e: B)
            System.out.print(e);

        while (i < A.length && j < B.length) {
            if (A[i] > B[j]) {
                count += A.length - i;
                C[k++] = B[j++];
            } else {
                C[k++] = A[i++];
            }
        }
        if (i == A.length && j < B.length)
            for (int l = j; l < B.length; l++)
                C[k++] = B[l];
        if (i < A.length && j == B.length)
            for (int l = i; l < A.length; l++)
                C[k++] = A[l];
        return count;
    }
}
python
# @Author: K1t0
# @Time: 2024/9/19
# @Description: 分治算法 逆序数

# 函数功能: SAC 算法
def SAC(list2):
    # 递归结束判定条件
    if len(list2) <= 1:
        return 0
    # 分组序列 A ,B Num_A Num_B
    A=[];B=[]
    Num_A=len(list2)//2
    Num_B=len(list2)-Num_A
    for i in range(len(list2)):
        if i<Num_A:
            A.append(list2[i])
        else:
            B.append(list2[i])
    rA=SAC(A)
    rB=SAC(B)
    r=MAC(A,B,list2)
    return r+rA+rB
# 函数功能:MAC 算法
def MAC(A,B,C):
    # A B C 下标
    i=0;j=0;k=0;count=0
    # A B 逆序判定
    while i<len(A) and j <len(B):
        if A[i]>B[j]:
            count+=len(A)-i
            C[k]=B[j]
            j+=1;k+=1
        else:
            C[k]=(A[i])
            i+=1;k+=1
    # 任何一方 结束,另一方全部加入C的序列中
    if i==len(A) and j<len(B):
        for c in range(j,len(B)):
            C[k]=B[c]
            k+=1
    if i<len(A) and j==len(B):
        for c in range(i,len(A)):
            C[k]=A[c]
            k+=1

    return count


if __name__=="__main__":
    # 接收序列
    list1=input("Input your list:").split()
    list2=[int(num) for num in list1 ]
    print(SAC(list2))
    print(list2)
一些理解

首先分治算法非常的简单,但是在写代码的时候总是会出现问题,首先就是因为这个参数传递的问题,因为java参数传递是引用传递,但是python传递是通过可变类型传递,因此我们需要传递一个参数进去才能达到引用的效果。

标签:count,int,分治,length,++,算法,序列,逆序
From: https://blog.csdn.net/m0_73255659/article/details/142381096

相关文章

  • 代码随想录算法训练营第十六天 | Javascript | 力扣Leetcode | 回溯 | 77. 组合、216.
    目录前言简介题目链接:77.组合题目链接:216.组合总和3题目链接:17.电话号码的字母组合前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄......
  • 代码随想录算法训练营第十五天 | Javascript | 继续二叉树的一天 | 力扣Leetcode | 补
    目录前言简介题目链接:501.二叉搜索树中的众数题目链接:236.二叉树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,......
  • 【集成学习|Bagging、Boosting 和 Stacking】三种常见的集成学习算法的联系与区别?以及
    【集成学习|Bagging、Boosting和Stacking】三种常见的集成学习算法的联系与区别?以及如何实现?【集成学习|Bagging、Boosting和Stacking】三种常见的集成学习算法的联系与区别?以及如何实现?附代码学习文章目录【集成学习|Bagging、Boosting和Stacking】三种常见的......
  • 安全帽识别算法、安全帽智能识别、不戴安全帽检测算法
    不戴安全帽检测算法是一种基于人工智能技术,用于实时监测和提醒工作人员是否正确佩戴安全帽的系统。以下是对不戴安全帽检测算法的详细介绍:1.技术原理 -数据采集与预处理:通过安装在施工现场或工厂车间等场所的摄像头收集图像数据,并进行必要的预处理,如去噪、图像增强等,以提高......
  • 【MATLAB源码-第227期】基于matlab的北方苍鹰优化算法(NGO)机器人栅格路径规划,输出做
    操作环境:MATLAB2022a1、算法描述鼠群优化算法(RatSwarmOptimization,RSO)简介鼠群优化算法(RatSwarmOptimization,RSO)是一种模仿鼠类群体觅食行为的优化算法。该算法属于群体智能算法,通过模拟鼠群在复杂环境中寻找食物的行为,来解决各种优化问题。鼠类在觅食过程中表现......
  • 超强合集||一行实现88个群智能算法优化混合核极限学习机HKELM的多特征输入单输出的数
    超强合集||一行实现88个群智能算法优化混合核极限学习机HKELM的多特征输入单输出的数据回归预测Matlab程序全家桶文章目录一、基本原理二、实验结果三、核心代码四、代码获取五、总结一、基本原理智能算法优化混合核极限学习机(HKELM)结合了智能优化技术,以进一步提......
  • 回归预测|2024年最新优化算法美洲狮优化器PO 基于美洲狮PO优化BP神经网络数据时间序列
    回归预测|2024年最新优化算法美洲狮优化器PO基于美洲狮PO优化BP神经网络数据时间序列算法完整Maltab程序有对比文章目录一、基本原理1.美洲狮优化算法(POA)简介2.BP神经网络(BPNeuralNetwork)简介3.PO-BP回归预测流程总结二、实验结果三、核心代码四、代码获取五......
  • Java中的文本聚类算法:如何进行大规模无监督文本分类
    Java中的文本聚类算法:如何进行大规模无监督文本分类大家好,我是微赚淘客系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!文本聚类是自然语言处理中的一个重要任务,旨在将大量的文本数据分成几个有意义的类别。由于文本数据的高维性和稀疏性,处理大规模无监督文本分类通常......
  • 优化算法(三)—模拟退火算法(附MATLAB程序)
    模拟退火算法(SimulatedAnnealing,SA)是一种基于概率的优化算法,旨在寻找全局最优解。该算法模拟金属退火过程中的物质冷却过程,逐渐降低系统的“温度”以达到全局优化的效果。它特别适用于解决复杂的组合优化问题。一、模拟退火算法基本原理模拟退火算法(SimulatedAnnealing,......
  • 优化算法(四)—蚁群算法(附MATLAB程序)
    蚁群算法(AntColonyOptimization,ACO)是一种模拟蚂蚁觅食行为的优化算法,由MarcoDorigo于1990年提出。它利用了蚂蚁在寻找食物的过程中通过释放信息素来相互影响的机制,以找到最优解或接近最优解。蚁群算法特别适用于解决组合优化问题,如旅行商问题(TSP)、调度问题等。一、基本原......