算法入门-分治法

算法
算法
发布日期:   2022-10-23
更新日期:   2022-10-27
文章字数:   7.8k
阅读时长:   33 分
阅读次数:  

分治法本质

分治算法，其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题，分而治之。

那么在现实生活中，什么样的问题才能使用分治法解决呢？简单来说，需要满足以下 3 个条件：

  1. 原问题可分解为若干个规模较小的相同子问题。
  2. 子问题相互独立。
  3. 子问题的解可以合并为原问题的解。

分治法解题步骤

  • 分解：将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
  • 治理：求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，而当子问题划分得足够小时，就可以用较简单的方法解决。
  • 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

递归是彰显分治法优势的利器。

二分搜索技术

算法设计：

问题描述：给定 n 个元素，这些元素是有序的（假定为升序），从中查找特定元素 x。

算法思想：将有序序列分成规模大致相等的两部分，然后取中间元素与特定查找元素 x 进行比较，如果 x 等于中间元素，则查找成功，算法终止；如果 x 小于中间元素，则在序列的前半部分继续查找，即在序列的前半部分重复分解和治理操作；否则，在序列的后半部分继续查找，即在序列的后半部分重复分解和治理操作。

算法设计：用一维数组 S[]存储该有序序列，设变量 low 和 high 表示查找范围的下界和上界，middle 表示查找范围的中间位置，x 为特定的查找元素。

  • 初始化。令 low=0，即指向有序数组 S[]的第一个元素；high=n−1，即指向有序数组S[]的最后一个元素。
  • middle=（low+high）/2，即指示查找范围的中间元素。
  • 判定 low≤high 是否成立，如果成立，转第 4 步，否则，算法结束。
  • 判断 x 与 S[middle]的关系。如果 x=S[middle]，则搜索成功，算法结束；如果x>S[middle]，则令 low=middle+1；否则令 high=middle−1，转为第 2 步。

代码实现：

//program 3-1
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int M=10000;
int x,n,i;
int s[M];

int BinarySearch(int n,int s[],int x)
{
   int low=0,high=n-1;  //low指向有序数组的第一个元素，high指向有序数组的最后一个元素
   while(low<=high)
   {
       int middle=(low+high)/2;  //middle为查找范围的中间值
       if(x==s[middle])  //x等于查找范围的中间值，算法结束
          return middle;
       else if(x>s[middle])   //x大于查找范围的中间元素，则从左半部分查找
              low=middle+1;
            else   //x小于查找范围的中间元素，则从右半部分查找
              high=middle-1;
    }
    return -1;
}

int main()
{
    cout<<"该数列中的元素个数n为：";
    while(cin>>n)
    {
        cout<<"请依次输入数列中的元素：";
        for(i=0;i<n;i++)
           cin>>s[i];
        sort(s,s+n);
        cout<<"排序后的数组为：";
        for(i=0;i<n;i++)
        {
           cout<<s[i]<<" ";
        }
        cout<<endl;
        cout<<"请输入要查找的元素：";
        cin>>x;
        i=BinarySearch(n,s,x);
        if(i==-1)
          cout<<"该数列中没有要查找的元素"<<endl;
        else
          cout<<"要查找的元素在第"<<i+1<<"位"<<endl;
    }
    return 0;
}

算法复杂度分析：

时间复杂度：

  1. 首先需要进行排序，调用 sort 函数，进行排序复杂度为 O(nlogn)，如果数列本身有序，那么这部分不用考虑。

  2. 如果我们用 T(n)来表示 n 个有序元素的二分查找算法时间复杂度，那么：

    • 当 n=1 时，需要一次比较，T(n)=O(1)

    • 当 n>1 时，特定元素和中间位置元素比较，需要 O(1)时间，如果比较不成功，那么需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变为 T(n/2)。

      image-20221023113347212

    • 当 n>1 时，可以递推求解如下。

      image-20221023113358680

      递推最终的规模为 1，令 n = 2x，则x = logn。

      image-20221023113505382

      二分查找算法的时间复杂度为 O(logn)。

**空间复杂度：**程序中变量占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为 O(1)。

优化拓展：

在上面程序中，我们采用 BinarySearch（int n，int s[]，int x）函数来实现二分搜索，那么能不能用递归来实现呢？因为递归有自调用问题，那么就需要增加两个参数 low 和 high 来标记搜索范围的开始和结束。

int recursionBS(int s[],int x,int low,int high)
{
   if(low>high)
      return -1;
   int middle = (low+high)/2
   if(x==middle)
      return middle
   else if (x<middle)
      return recursionBS(s[], x, low, middle-1)
      else
         return recursionBS(s[], x, middle+1,high)
}

空间复杂度：

在递归算法中，每一次递归调用都需要一个栈空间存储，那么我们只需要看看有多少次调用。

假设原问题的规模为 n，那么第一次递归就分为两个规模为 n/2 的子问题，这两个子问题并不是每个都执行，只会执行其中之一。

因为我们和中间值比较后，要么去前半部分查找，要么去后半部分查找；然后再把规模为 n/2的子问题继续划分为两个规模为 n/4 的子问题，选择其一；继续分治下去，最坏的情况会分治到只剩下一个数值，那么我们执行的节点数就是从树根到叶子所经过的节点，每一层执行一个，直到最后一层：

image-20221023120324903

递归调用最终的规模为 1，即 n/2x=1，则x=logn。假设阴影部分是搜索经过的路径，一共经过了 logn 个节点，也就是说递归调用了 logn 次。

因此，二分搜索递归算法的空间复杂度为 O(logn)。

合并排序

算法设计：

合并排序是采用分治策略实现对 n 个元素进行排序的算法，是分治法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略，过程大致分为：

  • 分解—将待排序元素分成大小大致相同的两个子序列。
  • 治理—对两个子序列进行合并排序。
  • 合并—将排好序的有序子序列进行合并，得到最终的有序序列。

image-20221023123323025

代码实现：

  1. 合并操作：

    设置 3 个工作指针 i、j、k（整型数）和一个辅助数组 B[]。其中，i 和 j 分别指向两个待排序子序列中当前待比较的元素，k 指向辅助数组 B[]中待放置元素的位置。比较 A[i]和A[j]，将较小的赋值给 B[k]，同时相应指针向后移动。如此反复，直到所有元素处理完毕。最后把辅助数组 B 中排好序的元素复制到 A 数组中：

    第 1 次比较 A[i]=4 和 A[j]=2，将较小元素 2 放入 B 数组中，j++，k++：

    image-20221023124616377

    while(i<=mid && j<=high) {//按从小到大存放到辅助数组B[]中
       if(A[i]<=A[j])
           B[k++]=A[i++];
       else
           B[k++]=A[j++];
   }

    当j>high 了，while 循环结束，但 A 数组还剩有元素（i≤mid）怎么办呢？直接放置到 B 数组就可以了：

    while(i<=mid) B[k++]=A[i++];//将数组中剩下的元素放置B中
   while(j<=high) B[k++]=A[j++];

    完整的合并程序如下：

    void Merge(int A[], int low, int mid, int high)
{
    int *B=new int[high-low+1];//申请一个辅助数组
    int i=low, j=mid+1, k=0;
    while(i<=mid && j<=high) {//按从小到大存放到辅助数组B[]中
        if(A[i]<=A[j])
            B[k++]=A[i++];
        else
            B[k++]=A[j++];
    }
    while(i<=mid) B[k++]=A[i++];//将数组中剩下的元素放置B中
    while(j<=high) B[k++]=A[j++];
    for(i=low, k=0; i<=high; i++)
        A[i]=B[k++];
    delete []B;
}

  2. 递归形式的合并排序算法

    将序列分为两个子序列，然后对子序列进行递归排序，再把两个已排好序的子序列合并成一个有序的序列。

    void MergeSort(int A[], int low, int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;//取中点
        MergeSort(A, low, mid);//对A[low:mid]中的元素合并排序
        MergeSort(A, mid+1, high);//对A[mid+1:high]中的元素合并排序
        Merge(A, low, mid, high);//合并
    }
}

完整代码：

//program 3-2
#include <iostream>
#include <cstdlib>
using namespace std;
void Merge(int A[], int low, int mid, int high)
{
    int *B=new int[high-low+1];//申请一个辅助数组
    int i=low, j=mid+1, k=0;
    while(i<=mid && j<=high) {//按从小到大存放到辅助数组B[]中
        if(A[i]<=A[j])
            B[k++]=A[i++];
        else
            B[k++]=A[j++];
    }
    while(i<=mid) B[k++]=A[i++];//将数组中剩下的元素放置B中
    while(j<=high) B[k++]=A[j++];
    for(i=low, k=0; i<=high; i++)
        A[i]=B[k++];
    delete []B;
}
void MergeSort(int A[], int low, int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;//取中点
        MergeSort(A, low, mid);//对A[low:mid]中的元素合并排序
        MergeSort(A, mid+1, high);//对A[mid+1:high]中的元素合并排序
        Merge(A, low, mid, high);//合并
    }
}
int main()
{
    int n, A[100];
    cout<<"请输入数列中的元素个数n为："<<endl;
    cin>>n;
    cout<<"请依次输入数列中的元素："<<endl;
    for(int i=0; i<n; i++)
       cin>>A[i];
    MergeSort(A,0,n-1);
    cout<<"合并排序结果："<<endl;
    for(int i=0;i<n;i++)
       cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}

算法复杂度分析：

时间复杂度：

  • 分解：这一步仅仅是计算出子序列的中间位置，需要常数时间 O(1)。
  • 解决子问题：递归求解两个规模为 n/2 的子问题，所需时间为 2T(n/2)。
  • 合并：Merge 算法可以在 O(n)的时间内完成。

所以总运行时间为：

image-20221023130510198

当 n>1 时，可以递推求解：

image-20221023130523916

递推最终的规模为 1，令 n = 2x ，则x = logn ，那么

image-20221023130559888

合并排序算法的时间复杂度为 O(nlogn)。

空间复杂度：

程序中变量占用了一些辅助空间，这些辅助空间都是常数阶的，每调用一个 Merge()，会分配一个适当大小的缓冲区，且退出时释放。最多分配大小为 n，所以空间复杂度为 O(n)。递归调用所使用的栈空间是O(logn)：

image-20221023130703054

递归调用时占用的栈空间是递归树的深度， n = 2x ，则 x = logn ，递归树的深度为 logn。

快速排序

它的基本思想是通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列。

算法设计：

快速排序的基本思想是基于分治策略的，其算法思想如下。

  1. 分解：先从数列中取出一个元素作为基准元素。以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。
  2. 治理：对两个子序列进行快速排序。
  3. 合并：将排好序的两个子序列合并在一起，得到原问题的解。

设当前待排序的序列为 R[low:high]，其中 low≤high，如果序列的规模足够小，则直接进行排序，否则分 3 步处理。

  1. 分解：在 R[low: high]中选定一个元素 R[pivot]，以此为标准将要排序的序列划分为两个序列 R[low:pivot−1]和 R[pivot+1:high]，并使用序列 R[low:pivot−1]中所有元素的值小于等于 R[pivot]，序列 R[pivot+1:high]中所有元素均大于 R[pivot]，此时基准元素已经位于正确的位置，它无需参加后面的排序：

    image-20221023225113169

  2. 治理：对于两个子序列 R[low:pivot−1]和 R[pivot+1:high]，分别通过递归调用快速排序算法来进行排序。

  3. 合并：由于对 R[low:pivot−1]和 R[pivot+1:high]的排序是原地进行的，所以在R[low:pivot−1]和 R[pivot+1:high]都已经排好序后，合并步骤无需做什么，序列 R[low:high]就已经排好序了。

如何分解是一个难题，因为如果基准元素选取不当，有可能分解成规模为 0 和 n−1 的两个子序列，这样快速排序就退化为冒泡排序了。

例如序列（30，24，5，58，18，36，12，42，39），第一次选取 5 做基准元素，第二次选取 12 做基准元素。这样做的效率是最差的，最理想的状态是把序列分解为两个规模相当的子序列，那么怎么选择基准元素呢？一般来说，基准元素选取有以下几种方法：

  • 取第一个元素。
  • 取最后一个元素。
  • 取中间位置元素。
  • 取第一个、最后一个、中间位置元素三者之中位数。
  • 取第一个和最后一个之间位置的随机数 k（low≤k≤high），选 R[k]做基准元素。

代码实现：

  1. 划分函数

    我们编写划分函数对原序列进行分解，分解为两个子序列，以基准元素 pivot 为界，左侧子序列都比 pivot 小，右侧子序列都比 pivot 大。先从右向左扫描，找小于等于 pivot 的数，找到后两者交换（r[i]和 r[j]交换后 i++）；再从左向右扫描，找比基准元素大的数，找到后两者交换（r[i]和 r[j]交换后 j−−）。扫描交替进行，直到 i=j 停止，返回划分的中间位置 i。

    int Partition(int r[],int low,int high)//划分函数
{
    int i=low,j=high,pivot=r[low];//基准元素
    while(i<j)
    {
        while(i<j&&r[j]>pivot) j--;//向左扫描
        if(i<j)
        {
            swap(r[i++],r[j]);//r[i]和r[j]交换后i+1右移一位
        }
        while(i<j&&r[i]<=pivot) i++;//向右扫描
        if(i<j)
        {
            swap(r[i],r[j--]);//r[i]和r[j]交换 后j-1左移一位
        }
    }
    return i;//返回最终划分完成后基准元素所在的位置
}

  2. 快速排序递归算法

    首先对原序列执行划分，得到划分的中间位置 mid，然后以中间位置为界，分别对左半部分（low，mid−1）执行快速排序，右半部分（mid+1，high）执行快速排序。递归结束的条件是 low≥high。

    void QuickSort(int R[],int low,int high)//实现快排算法
{
    int mid;
    if(low<high)
    {
        mid=Partition(R,low,high); //基准位置
        for(int i=low;i<=high;i++)
          cout<<R[i]<<" ";
        cout<<endl;
        QuickSort(R,low,mid-1);//左区间递归快排
        QuickSort(R,mid+1,high);//右区间递归快排
    }
}

完整代码：

//program 3-3
#include <iostream>
using namespace std;
int Partition(int r[],int low,int high)//划分函数
{
    int i=low,j=high,pivot=r[low];//基准元素
    while(i<j)
    {
        while(i<j&&r[j]>pivot) j--;//向左扫描
        if(i<j)
        {
            swap(r[i++],r[j]);//r[i]和r[j]交换后i+1右移一位
        }
        while(i<j&&r[i]<=pivot) i++;//向右扫描
        if(i<j)
        {
            swap(r[i],r[j--]);//r[i]和r[j]交换 后j-1左移一位
        }
    }
    return i;//返回最终划分完成后基准元素所在的位置
}


void QuickSort(int R[],int low,int high)//实现快排算法
{
    int mid;
    if(low<high)
    {
        mid=Partition(R,low,high); //基准位置
        for(int i=low;i<=high;i++)
          cout<<R[i]<<" ";
        cout<<endl;
        QuickSort(R,low,mid-1);//左区间递归快排
        QuickSort(R,mid+1,high);//右区间递归快排
    }
}
int main()
{
    int a[100];
    int i,N;
    cout<<"请先输入要排序的数据的个数：";
    cin>>N;
    cout<<"请输入要排序的数据：";
    for(i=0;i<N;i++)
        cin>>a[i];
    cout<<endl;
    QuickSort(a,0,N-1);
    cout<<"排序后的序列为："<<endl;
    for(i=0;i<N;i++)
        cout<<a[i]<<" " ;
    cout<<endl;
    return 0;
}

算法复杂度分析：

最好时间复杂度：

  • 分解：划分函数 Partition 需要扫描每个元素，每次扫描的元素个数不超过 n，因此时间复杂度为 O(n)。
  • 解决子问题：在最理想的情况下，每次划分将问题分解为两个规模为 n/2 的子问题，递归求解两个规模为 n/2 的子问题，所需时间为 2T(n/2)。
  • 合并：因为是原地排序，合并操作不需要时间复杂度。

所以总运行时间为：

image-20221023231955341

当 n>1 时，可以递推求解：

image-20221023232011137

递推最终的规模为 1，令 n = 2x，则x = logn，则快速排序算法最好的时间复杂度为 O(nlogn)。

空间复杂度：

程序中变量占用了一些辅助空间，这些辅助空间都是常数阶的，递归调用所使用的栈空间是 O(logn)。

最坏时间复杂度：

  • 分解：划分函数 Partition 需要扫描每个元素，每次扫描的元素个数不超过 n，因此时间复杂度为 O(n)。

  • 解决子问题：在最坏的情况下，每次划分将问题分解后，基准元素的左侧（或者右侧）没有元素，基准元素的另一侧为 1 个规模为 n−1 的子问题，递归求解这个规模为 n−1 的子问题，所需时间为 T(n−1)。

  • 合并：因为是原地排序，合并操作不需要时间复杂度。

    所以总运行时间为：

    image-20221023233135333

    当 n>1 时，可以递推求解如下：

    image-20221023233158324

    快速排序算法最坏的时间复杂度为 O(n2 )。

平均时间复杂度：

假设我们划分后基准元素的位置在第 k（k=1，2，…，n）个，则：

image-20221023233714369

由归纳法可以得出，T(n)的数量级也为 O(nlogn)。快速排序算法平均情况下，时间复杂度为 O(nlogn)，递归调用所使用的栈空间也是 O(logn)。

优化拓展：

从上述算法可以看出，每次交换都是在和基准元素进行交换，实际上没必要这样做，我们的目的就是想把原序列分成以基准元素为界的两个子序列，左侧子序列小于等于基准元素，右侧子序列大于基准元素。

那么有很多方法可以实现，我们可以从右向左扫描，找小于等于 pivot 的数 R[j]，然后从左向右扫描，找大于 pivot 的数 R[i]，让 R[i]和 R[j]交换，一直交替进行，直到 i 和 j 碰头为止，这时将基准元素与 R[i]交换即可。这样就完成了一次划分过程，但交换元素的个数少了很多。

int Partition2(int r[],int low,int high)//划分函数
{
    int i=low,j=high,pivot=r[low];//基准元素
    while(i<j)
    {
        while(i<j&&r[j]>pivot) j--;//向左扫描
        while(i<j&&r[i]<=pivot) i++;//向右扫描
        if(i<j)
        {
            swap(r[i++],r[j--]);//r[i]和r[j]交换
        }
    }
    if(r[i]>pivot)
    {
        swap(r[i-1],r[low]);//r[i-1]和r[low]交换
        return i-1;//返回最终划分完成后基准元素所在的位置
    }
    swap(r[i],r[low]);//r[i]和r[low]交换
    return i;//返回最终划分完成后基准元素所在的位置
}

大整数乘法

在解决两个大的整数相乘时，我们可以将一个大的整数乘法分而治之，将大问题变成小问题，变成简单的小数乘法再进行合并。

算法分析：

  • 分解：首先将 2 个大整数 a（n 位）、b（m 位）分解为两部分：

    image-20221025105405840

    ah 表示大整数 a 的高位，al 表示大整数 a 的低位。bh 表示大整数 b 的高位，bl 表示大整数 b 的低位。

    2 个大整数 a（n 位）、b（m 位）相乘转换成了 4 个乘法运算 *ah bh、 *ah bl、 *al bh、 *al bl ，而乘数的位数变为了原来的一半。

  • 求解子问题

    继续分解每个乘法运算，直到分解有一个乘数为 1 位数时停止分解，进行乘法运算并记录结果。

  • 合并

    将计算出的结果相加并回溯，求出最终结果。

具体如何处理呢？

  1. 首先将两个大数以字符串的形式输入，转换成数字后，倒序存储在数组 s[]中，l 用来表示数的长度，c 表示次幂。两个大数的初始次幂为 0。

    倒序存储的原因——因为乘法加法运算中有可能产生进位，倒序存储时可以让进位存储在数组的末尾

    • cp()函数：用于将一个 n 位的数分成两个 n/2 的数并存储，记录它的长度和次幂。
    • mul()函数：用于将两个数进行相乘，不断地进行分解，直到有一个乘数为 1 位数时停止分解，进行乘法运算并记录结果。
    • add()函数：将分解得到的数进行相加合并。

  2. 乘法运算：

    image-20221025110347497

    3 首先和 1 相乘得到 3 存储在下面数组的第 0 位；然后 3 和 4 相乘得到 12，先存储先存储 12%10=2，然后存储进位 12/10=1，这样乘法运算的结果是 321，注意是倒序，实际含义是 3×41=123；两数相乘时，结果的次幂是两个乘数次幂之和，3×103 ×41×103 =123×106。

代码实现：

  1. 数据结构

    将两个大数以字符串的形式输入，然后定义结构体 Node，其中 s[]数组用于存储大数，注意是倒序存储！l 用于表示长度，c 表示次幂。两个大数的初始次幂为 0。

    #include <stdlib.h>
#include <cstring>
#include <iostream>
using namespace std;

#define M 100

char sa[1000];
char sb[1000];

typedef struct _Node
{
    int s[M];
    int l;            //代表字符串的长度
    int c;
} Node,*pNode;

  2. 划分函数

    其中，cp()函数用于将一个 n 位的数分成两个 n/2 的数并存储，记录它的次幂。

    void cp(pNode src, pNode des, int st, int l)
{
    //src 表示待分解的数结点，des 表示分解后得到的数结点
    //st 表示从 src 结点数组中取数的开始位置，l 表示取数的长度
    int i, j;
    for(i=st, j=0; i<st+l; i++, j++)//从 src 结点数组中 st 位置开始，取 l 个数
    {
        des->s[j] = src->s[i];//将这些数放入到 des 结点的数组中
    }
    des->l = l;//des 长度等于取数的长度
    des->c = st + src->c;  //des 次幂等于开始取数的位置加上 src 次幂

}

  3. 乘法运算

    定义的 mul()函数用于将两个数进行相乘，不断地进行分解，直到有一个乘数为 1 位时停止，让这两个数相乘，并记录结果回溯。

    void mul(pNode pa, pNode pb, pNode ans)
{
    int i, cc, w;
    int ma = pa->l>>1, mb = pb->l>>1; //长度除2
    Node ah, al, bh, bl;
    Node t1, t2, t3, t4, z;
    pNode temp;

    if(!ma || !mb) //如果其中个数为1
    {
    //如果!ma 说明 ma=0，即 a 的长度为 1，该乘数为 1 位数
    //如果!mb 说明 mb=0，即 b 的长度为 1，该乘数为 1 位数
        if(!ma)   //如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度
        {
            temp = pa;
            pa = pb;
            pb = temp;
        }
        ans->c = pa->c + pb->c;
        w = pb->s[0];
        cc = 0;     //此时的进位为c
        for(i=0; i < pa->l; i++)
        {
            ans->s[i] = (w*pa->s[i] + cc)%10;
            cc= (w*pa->s[i] + cc)/10;
        }
        if(cc)
            ans->s[i++] = cc; //如果到最后还有进位，则存入结果
        ans->l = i;          //记录结果的长度
        return;
    }
    //分治的核心
    cp(pa, &ah, ma, pa->l-ma);  //先分成4部分al,ah,bl,bh
    cp(pa, &al, 0, ma);
    cp(pb, &bh, mb, pb->l-mb);
    cp(pb, &bl, 0, mb);

    mul(&ah, &bh, &t1);     //分成4部分相乘
    mul(&ah, &bl, &t2);
    mul(&al, &bh, &t3);
    mul(&al, &bl, &t4);

    add(&t3, &t4, ans);
    add(&t2, ans, &z);
    add(&t1, &z, ans);
}

  4. 合并函数

    add()函数将分解得到的数进行相加合并。

    void add(pNode pa, pNode pb, pNode ans)
{
    int i,cc,k,palen,pblen,len;
    int ta, tb;
    pNode temp;
    if((pa->c<pb->c))   //保证Pa的次幂大
    {
        temp = pa;
        pa = pb;
        pb = temp;
    }
    ans->c = pb->c;
    cc = 0;
    palen=pa->l + pa->c;
    pblen=pb->l + pb->c;
    if(palen>pblen)
        len=palen;
    else
        len=pblen;
    k=pa->c - pb->c;
    for(i=0; i<len-ans->c; i++) //结果的长度最长为pa，pb之中的最大长度减去最低次幂
    {
        if(i<k)
            ta = 0;
        else
            ta = pa->s[i-k];//次幂高的补0，大于低的长度后与0进行计算
        if(i<pb->l)
            tb = pb->s[i];
        else
            tb = 0;
        if(i>=pa->l+k)
            ta = 0;
        ans->s[i] = (ta + tb + cc)%10;
        cc = (ta + tb + cc)/10;
    }
    if(cc)
        ans->s[i++] = cc;
    ans->l = i;
}

完整代码：

//program 3-4
#include <stdlib.h>
#include <cstring>
#include <iostream>
using namespace std;

#define M 100

char sa[1000];
char sb[1000];

typedef struct _Node
{
    int s[M];
    int l;            //代表字符串的长度
    int c;
} Node,*pNode;

void cp(pNode src, pNode des, int st, int l)
{
    int i, j;
    for(i=st, j=0; i<st+l; i++, j++)
    {
        des->s[j] = src->s[i];
    }
    des->l = l;
    des->c = st + src->c;  //次幂

}

/*
分治法 大数乘法
X = A*10^n + B
Y = C*10^m + D
X*Y = A*C*10^(n+m) + A*D*10^n + B*C*10^m + B*D
*/

void add(pNode pa, pNode pb, pNode ans)
{
    int i,cc,k,palen,pblen,len;
    int ta, tb;
    pNode temp;
    if((pa->c<pb->c))   //保证Pa的次幂大
    {
        temp = pa;
        pa = pb;
        pb = temp;
    }
    ans->c = pb->c;
    cc = 0;
    palen=pa->l + pa->c;
    pblen=pb->l + pb->c;
    if(palen>pblen)
        len=palen;
    else
        len=pblen;
    k=pa->c - pb->c;
    for(i=0; i<len-ans->c; i++) //结果的长度最长为pa，pb之中的最大长度减去最低次幂
    {
        if(i<k)
            ta = 0;
        else
            ta = pa->s[i-k];//次幂高的补0，大于低的长度后与0进行计算
        if(i<pb->l)
            tb = pb->s[i];
        else
            tb = 0;
        if(i>=pa->l+k)
            ta = 0;
        ans->s[i] = (ta + tb + cc)%10;
        cc = (ta + tb + cc)/10;
    }
    if(cc)
        ans->s[i++] = cc;
    ans->l = i;
}

void mul(pNode pa, pNode pb, pNode ans)
{
    int i, cc, w;
    int ma = pa->l>>1, mb = pb->l>>1; //长度除2
    Node ah, al, bh, bl;
    Node t1, t2, t3, t4, z;
    pNode temp;

    if(!ma || !mb) //如果其中个数为1
    {
        if(!ma)   //如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度
        {
            temp = pa;
            pa = pb;
            pb = temp;
        }
        ans->c = pa->c + pb->c;
        w = pb->s[0];
        cc = 0;     //此时的进位为c
        for(i=0; i < pa->l; i++)
        {
            ans->s[i] = (w*pa->s[i] + cc)%10;
            cc= (w*pa->s[i] + cc)/10;
        }
        if(cc)
            ans->s[i++] = cc; //如果到最后还有进位，则存入结果
        ans->l = i;          //记录结果的长度
        return;
    }
    //分治的核心
    cp(pa, &ah, ma, pa->l-ma);  //先分成4部分al,ah,bl,bh
    cp(pa, &al, 0, ma);
    cp(pb, &bh, mb, pb->l-mb);
    cp(pb, &bl, 0, mb);

    mul(&ah, &bh, &t1);     //分成4部分相乘
    mul(&ah, &bl, &t2);
    mul(&al, &bh, &t3);
    mul(&al, &bl, &t4);

    add(&t3, &t4, ans);
    add(&t2, ans, &z);
    add(&t1, &z, ans);
}

int main()
{
    Node ans,a,b;
    cout << "输入大整数 a:"<<endl;
    cin >> sa;
    cout << "输入大整数 b:"<<endl;
    cin >> sb;
    a.l=strlen(sa);//sa,sb以字符串进行处理
    b.l=strlen(sb);
    int z=0,i;
    for(i = a.l-1; i >= 0; i--)
        a.s[z++]=sa[i]-'0';             //倒向存储
    a.c=0;
    z=0;
    for(i = b.l-1; i >= 0; i--)
        b.s[z++] = sb[i]-'0';
    b.c = 0;
    mul(&a, &b, &ans);
    cout << "最终结果为：";
    for(i = ans.l-1; i >= 0; i--)
        cout << ans.s[i];         //ans用来存储结果，倒向存储
    cout << endl;
    return 0;
}

算法复杂度分析：

时间复杂度：

我们假设大整数 a、b 都是 n 位数，根据分治策略， ab 相乘将转换成了 4 个乘法运算ah×bh、ah×bl、al×bh、al×bl，而乘数的位数变为了原来的一半。直到最后递归分解到其中一个乘数为 1 位为止，每次递归就会使数据规模减小为原来的一半。假设两个 n 位大整数相乘的时间复杂度为 T(n)，则：

image-20221025113307465

当 n>1 时，可以递推求解如下：

image-20221025113650106

递推最终的规模为 1，令 n = 2x 则x = logn，所以大整数乘法的时间复杂度为O(n2)

空间复杂度：

程序中变量占用了一些辅助空间，都是常数阶的，但合并时结点数组占用的辅助空间为 O(n)，递归调用所使用的栈空间是 O(logn)，大整数乘法的空间复杂度为O(n2)

优化拓展：

如果两个大整数都是 n 位数，那么有：

image-20221025114210441

还记得快速算出 1+2+3+…+100 的小高斯吗？这孩子长大以后更聪明，他把 4 次乘法运算变成了 3 次乘法：

image-20221025114312929

这样公式中，只需要进行 3 次乘法。

那么时间复杂度为：

image-20221025114401541

当 n>1 时，可以递推求解如下：

image-20221025114416856

递推最终的规模为 1，令 n = 2x ，则 x = logn，那么有：

image-20221025114522459

优化改进后的大整数乘法的时间复杂度从 O(n2 )降为 O(n1.59 )，这是一个巨大的改进！

但是需要注意：在上面的公式中，A 和 B 必须 2n 位。很容易证明，如果不为 2n，那么 A或者 B 在分解过程中必会出现奇数，那么 ac 和（（a−b）（d−c）+ac+b*d）的次幂就有可能不同，无法变为 3 次乘法了，解决方法也很简单，只需要补齐位数即可，在数前（高位）补 0。

分治算法复杂度求解秘籍

分治法的道理非常简单，就是把一个大的复杂问题分为 a（a>1）个形式相同的子问题，这些子问题的规模为 n/b，如果分解或者合并的复杂度为 f(n)，那么总的时间复杂度可以表示为：

image-20221025114832010

上面的求解方式都是递推求解，写出其递推式，最后求出结果。

文章作者: QT-7274
文章链接: https://qt-7274.github.io/2022/10/23/suan-fa-ru-men-fen-zhi-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 QT-7274 !
算法
赏
评论
  目录