L5_07 分治算法

一、分治算法概述

分治算法（Divide and Conquer）是一种重要的算法设计策略，其核心思想是将一个复杂的问题分解成若干个规模较小的相同子问题，递归地解决这些子问题，然后将子问题的解合并得到原问题的解。

1.1 分治算法的三个步骤

1. 分解（Divide）：将问题分解为若干个规模较小的子问题
2. 解决（Conquer）：递归地解决每个子问题
3. 合并（Combine）：将子问题的解合并为原问题的解

1.2 分治算法的特点

• 优点：

  • 可以将复杂问题简化
  • 适合并行处理
  • 时间复杂度通常较低

• 缺点：

  • 可能需要较多的内存空间
  • 合并步骤可能比较复杂

---

二、归并排序

归并排序是分治算法的经典应用，它将数组分成两半，分别排序后再合并。

2.1 算法步骤

1. 将数组分成左右两半
2. 递归地对左右两半进行排序
3. 合并两个有序的子数组

2.2 代码实现

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    vector<int> L(n1), R(n2);
    
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[mid + 1 + j];
    }
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        merge(arr, left, mid, right);
    }
}

2.3 复杂度分析

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

---

三、快速排序

快速排序也是分治算法的经典应用，它选择一个基准元素，将数组分成两部分，左边小于基准，右边大于基准。

3.1 算法步骤

1. 选择一个基准元素（pivot）
2. 分区：将数组分成两部分，左边小于等于基准，右边大于基准
3. 递归地对左右两部分进行排序

3.2 代码实现

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

3.3 复杂度分析

• 平均时间复杂度：O(n log n)
• 最坏时间复杂度：O(n^2)（当数组已经有序时）
• 空间复杂度：O(log n)（递归栈空间）

---

四、分治算法的其他应用

4.1 最大子数组和（Kadane算法的分治版本）

int maxCrossingSum(vector<int>& arr, int left, int mid, int right) {
    int sum = 0;
    int leftSum = INT_MIN;
    
    for (int i = mid; i >= left; --i) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }
    
    sum = 0;
    int rightSum = INT_MIN;
    
    for (int i = mid + 1; i <= right; ++i) {
        sum += arr[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }
    
    return max({leftSum, rightSum, leftSum + rightSum});
}

int maxSubArray(vector<int>& arr, int left, int right) {
    if (left == right) {
        return arr[left];
    }
    
    int mid = left + (right - left) / 2;
    
    return max({
        maxSubArray(arr, left, mid),
        maxSubArray(arr, mid + 1, right),
        maxCrossingSum(arr, left, mid, right)
    });
}

4.2 二分搜索

int binarySearch(vector<int>& arr, int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, right, target);
    } else {
        return binarySearch(arr, left, mid - 1, target);
    }
}

---

五、分治算法的适用条件

分治算法适用于满足以下条件的问题：

1. 问题可以分解：原问题可以分解为若干个规模较小的相同子问题
2. 子问题相互独立：子问题之间没有依赖关系，可以独立求解
3. 子问题的解可以合并：可以将子问题的解合并得到原问题的解
4. 递归终止条件明确：存在基本情况，不需要继续分解

---

六、分治算法与其他算法的比较

算法类型	特点	典型应用
分治	分解-解决-合并	归并排序、快速排序
动态规划	重叠子问题、最优子结构	最短路径、背包问题
贪心	局部最优推导全局最优	最小生成树、哈夫曼编码

---

七、总结

分治算法是一种重要的算法设计策略，通过将问题分解为子问题来简化求解过程。归并排序和快速排序是分治算法的经典应用，掌握分治思想对于解决复杂算法问题非常重要。