数据结构与算法——分治

2023-12-22 19:22:40

算法——分治法

1 算法思想

将一个规模为 n 的问题划分为 k 个规模较小的子问题，这些子问题独立且与原问题相同。然后通过递归解决这些子问题，将子问题的解合并得到原问题的解。

\[T(n)=\begin{cases}O(1) & n=1 \\ kT(\lfloor n/m \rfloor)+f(n) & n>1\end{cases} \]

2 例子

2.1 二分搜索

二分搜索就是典型的使用分治法的例子。
给定已经排序好的 n 个元素集合 a[0:n-1]，找出其中一个特定元素 x。二分法将 n 个元素分为数量大致相同的两个部分，取 a[n/2]与 x 进行比较。
如果\(x<a[n/2]\)，则在 a[0:n/2]进行搜索；
如果\(x=a[n/2]\)，则找到 x;
如果\(x>a[n/2]\),则在 a[n/2:n-1]进行搜索。具体算法例子如下。

template<typename T>
int BinarySearch(T a[], int lo, int hi){
    //找到x在集合中的位置，否则返回-1
    while(lo <= hi){
        int mid = lo + (hi - lo)/2;
        if(x == a[mid])   return mid;
        else if(x < a[mid])     hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

2.2 大整数乘法

设 X 和 Y 为 n 位二进制整数，要计算他们的乘积 XY。如果用一位一位相乘的方法需要\(O(n^2)\)的复杂度。如果采用分治能够更有效率的计算大整数。

将 X 和 Y 分别分为两段，每段的长为 n/2(X 的高位和低位记为 A 和 B，Y 的高位和低位记为 C 和 D)。由此，可计算出

\(X=A*2^{\frac{n}{2}}+B,\)

\(Y=C*2^{\frac{n}{2}}+D，\)

\(XY=(AC*2^{\frac{n}{2}}+(AD+BC)*2^{\frac{n}{2}}+BD)\)。
但是如果这样计算 XY，如需要 4 次 n/2 的乘法，3 次不超过 2n 位的加法，两次移位，并没有比直接计算更有效。因此我们通过分解 AD+BC 优化计算，

\[XY=(AC*2^{\frac{n}{2}}+((A-B)(D-C)+BD+AC)*2^{\frac{n}{2}}+BD) \]

如此只需要进行三次乘法，复杂度可以降低到\(O(n^{log3})\)。

typedef long long ll;
ll multipy(ll x, ll y, int num)
{
    int s = (x > 0) && (y > 0) ? 1 : -1;
    x = (x > 0) ? x : -x;
    y = (y > 0) ? y : -y;
    if (num == 0)	//递归出口
        return 0;
    else if (num == 1)	//一位数直接相乘
        return s * x * y;
    else
    {
        ll A = x / (int)pow(10, (int)(num / 2));	//获取X的高位
        ll B = x % (int)pow(10, (int)(num / 2));	//获取X的低位
        ll C = y / (int)pow(10, (int)(num / 2));	//获取Y的高位
        ll D = y % (int)pow(10, (int)(num / 2));	//获取Y的低位

        ll AC = multipy(A, C, (int)(num / 2));		//递归计算AC
        ll BD = multipy(B, D, (int)(num / 2));		//递归计算BD
        ll ABDC = multipy(A - B, D - C, (int)(num / 2)) + AC + BD;	//递归计算(A-B)(D-C)
        return s * (ll)(AC * (int)pow(10, (int)(num / 2) + (int)(num / 2)) + ABDC * (int)pow(10, (int)(num / 2)) + BD);
    }
}

2.3 快速排序

快速排序也是基于分治思想的一种排序方法。

对于给定的数组 a[p:r]，按照下列步骤进行排序。

寻找分隔点将数组 a[p:r]分成三段，任一元素都小于分隔点的子数组，分隔点，任一元素都大于分隔点的子数组。
递归的对子数组进行快速排序
合并数组

快速排序的运行时间与划分是否对称有关。
最坏的情况下每次划分的两个区域的数量分别包含 n-1 个元素和 1 个元素，此时 Partition 的时间复杂度为\(O(n)\)，如果每次划分都是这种情况，那快速排序的复杂度会达到\(O(n^2)\)。
在最好的情况下，每次划分的基准都恰好为中值，每次划分的两个区域大小都为 n/2，此时快速排序的复杂度会降到\(O(nlogn)\)。
经过证明，在平均情况下，快速排序的时间复杂度也为\(O(nlogn)\)。

template <typename T>
int Partition(T a[], int lo, int hi)
{
    int i = lo, j = hi + 1;
    T temp = a[lo];
    while (true)
    {
        while (a[++i] < temp)	//将小于分隔点的放在左段
            ;
        while (a[--j] > temp)	//将大于分隔点的放在左段
            ;
        if (i >= j)
            break;
        swap(a[i], a[j]);
    }
    swap(a[lo], a[j]);
    return j;
}

template <typename T>
void QuickSort(T a[], int lo, int hi)
{
    if (lo < hi)
    {
        int j = Partition(a, lo, hi);	//寻找分隔点
        QuickSort(a, lo, j - 1);	//左段进行排序
        QuickSort(a, j + 1, hi);	//右段进行排序
    }
}

2.4 最接近点对问题

给定平面上的 n 个点，找出其中的一对点，使得在 n 个点组成的所有点对中，该点对的距离最小。

最直观的解法就是将每一个点与其他 n-1 个点进行比较，找出最小的距离，这样的复杂度为\(O(n^2)\)。

如果我们采用分治的方法就能将复杂度降低到\(O(nlogn)\)。

在一维情况下，我们用 m 点将集合 S 分为 S1 和 S2 两个集合。
这样所有的 S1 中的点 p 和 S2 中的 q，有 p<q。递归的在 S1 和 S2 上找到最近点对，并设 d=min(|p1-p2|,|q1-q2|)。则 S 中的最近点对或者是(p1,p2)，(q1,q2)或者是(p3,q3)。如果 S 的最近点对是(p3,q3)，则 p3 和 q3 与 m 的距离不超过 d，且在区间(m-d,d]和(d,m+d]各有且仅有一个点。这样就能再线性时间完成合并。

而在二维的情况下，由上图可见，形成的宽为 2d 的带状区间，最多可能有 n 个点，合并时间最坏情况下为\(n^2\)。但是，P1 和 P2 中的点具有以下稀疏的性质，对于 P1 中的任意一点，P2 中的点必定落在一个\(d*2d\)的矩形中，且最多只需检查六个点。

struct Point{
    double x,y;
}point[N];

int n;
int temp[N];

double Cpair(int left, int right){
    double d = 1e20;
    //递归出口
    if(left==right) return d;
    if(left+1 == right) return dis(left,right);
    int mid = left + (right-left)/2;
    double d1 = Cpair(left,mid);	//递归寻找左边最短距离
    double d2 = Cpair(mid+1,right);	//递归寻找右边最短距离
    d = min(d1,d2);
    int i,j,k=0;
    //寻找距离中线在d以内的点的集合
    for(i = left; i <= right; ++i){
        if(fabs(point[mid].x-point[y].x)<=d)
            temp[k++] = i;
    }
    sort(temp,temp+k);
    //线性扫描
    for(i = 0; i < k; i++){
        for(j = i + 1; j <k&&point[temp[i]].y-point[temp[i]].y<d;j++){
            double d3 = dis(temp[i],temp[j]);
            if(d>d3)
                d=d3;
        }
    }
    return d;
}

码农公寓