当前位置：首页 > article >正文

算法-分治和逆序

article 2024/9/21 5:23:57

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

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

分解（Divide）：将原问题分解为若干个规模较小的相同问题。
解决（Conquer）：递归地解决这些子问题。如果子问题足够小，可以直接解决。
合并（Combine）：将子问题的解合并以得到原问题的解。

时间复杂度

最佳情况：如果每次分区操作都能将数组均匀地分成两个相等的部分，那么快速排序的时间复杂度是最优的。在这种情况下，递归的深度是 logn（其中 n 是数组的长度），每一层的工作时间是 O(n)。因此，总的时间复杂度是 �(�log⁡�)O(nlogn)。
平均情况：在大多数情况下，快速排序的性能接近最佳情况，尽管可能不是完全均匀的划分。平均情况下的时间复杂度也是 O(nlogn)。
最坏情况：如果每次分区操作都极不均匀，例如每次只将数组分成一个元素和其余元素两部分，那么递归的深度将是 �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)