程序员求职经验分享与学习资料整理平台

网站首页 > 文章精选 正文

什么是分治算法?（什么是分治算法）

balukai 2025-06-24 11:43:49 文章精选 2 ℃

分治算法的思想到底是什么？能不能用通俗易懂的方式讲解一下？

分治算法是一种重要的算法设计策略，其核心思想是"分而治之"，即将一个大问题分解成若干个相似的子问题，递归求解子问题，最后合并子问题的解得到原问题的解。

1.基本思想

1）分治算法的基本思想

分治算法通常包含三个步骤：

  1. 分解（Divide）：将原问题分解成若干个规模较小的子问题。
  2. 解决（Conquer）：递归求解子问题。如果子问题足够小，则直接求解。
  3. 合并（Combine）：将子问题的解合并，得到原问题的解。

分治算法 =分（Divide） +治（Conquer） +合（Combine）

  • 分解原则：
    • 子问题必须与原问题同构（相同性质）
    • 子问题之间应尽可能独立
    • 分解后的规模应显著减小（通常至少减半）

2）递归方程建立

通用形式：

T(n)=a·T(nb)+f(n)

其中：

  • a：子问题数量
  • nb：子问题规模
  • f(n)：分解+合并的代价

2.归并排序

归并排序是一种基于分治思想的经典排序算法，其时间复杂度为O(nlogn)，是稳定排序算法。

示例：假设要排序数组是[38, 27, 43, 3, 9, 82, 10]

第一步：分解过程（分）

原始数组: [38, 27, 43, 3, 9, 82, 10]第一次分割: [38, 27, 43, 3] 和 [9, 82, 10]第二次分割:   [38, 27] 和 [43, 3]  [9, 82] 和 [10]第三次分割:  [38] 和 [27]  [43] 和 [3]  [9] 和 [82]  [10] (已经是最小单元)

第二步：合并过程（合）

合并 [38] 和 [27] → [27, 38]合并 [43] 和 [3] → [3, 43]合并 [27, 38] 和 [3, 43] → [3, 27, 38, 43] (左半部分完成)合并 [9] 和 [82] → [9, 82]合并 [9, 82] 和 [10] → [9, 10, 82] (右半部分完成)最后合并 [3, 27, 38, 43] 和 [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

实现代码如下：

#include#includeusing namespace std;void merge(vector<int>& arr,int left,int mid,int right){	    std::vector<int> L(arr.begin() + left, arr.begin() + mid + 1);    std::vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);        int i = 0, j = 0, k = left;        // 比较两个数组的元素，取较小的放入原数组    while (i < L.size() && j < R.size()) {        if (L[i] <= R[j]) {            arr[k] = L[i];            i++;        } else {            arr[k] = R[j];            j++;        }        k++;    }        // 将剩余元素拷贝到原数组    while (i < L.size()) {        arr[k] = L[i];        i++;        k++;    }        while (j < R.size()) {        arr[k] = R[j];        j++;        k++;    }		}void merge_sort(vector<int>& arr,int left,int right){		if(left>=right){		return;	}	        //因为是递归，left 在非首次可能不是0，所以mid 如下式	int mid = left + (right - left)/2;		merge_sort(arr,left,mid);	merge_sort(arr,mid+1,right);	merge(arr,left,mid,right);	}int main(){		vector<int> array ={1,3,9,2,4,5,7};	merge_sort(array,0,array.size()-1);		for (int num : array) {        std::cout << num << " ";    }	}

3.快速排序

快速排序是一种高效的排序算法，采用分治策略，平均时间复杂度为O(n log n)，最坏情况下为O(n^2)。核心思想：选一个数，小的放左边，大的放右边，递归搞定。

算法步骤：

1.选择基准值（pivot）：从数组中选择一个元素作为基准

2.分区（partition）：将数组分为两部分，使得：

  • 左边部分的元素都小于等于基准值
  • 右边部分的元素都大于基准值

3.递归排序：对左右两部分递归地应用快速排序。

示例：初始数组: [38, 27, 43, 3, 9, 82, 10]

第一次分区（pivot=10）将 ≤10 的数移到左边，>10 的数留在右边：交换后：[3, 9, 10, 27, 38, 82, 43]分区结果：[3, 9] 和 [27, 38, 82, 43]（基准值 10 已归位）递归处理左子数组 [3, 9]（pivot=9）分区后：[3, 9]（已有序）递归处理右子数组 [27, 38, 82, 43]（pivot=43）分区后：[27, 38, 43, 82]进一步分割：[27, 38] 和 [82]最终排序结果: [3, 9, 10, 27, 38, 43, 82]

实现代码如下：

#include#includeusing namespace std;void quick_sort(vector<int>& arr, int low, int high) {    if (low >= high) return;  // 递归终止条件        int pivot = arr[high];    // 选最右为基准    int i = low - 1;          // i标记≤pivot的边界        for (int j = low; j < high; j++) {        if (arr[j] <= pivot) {            i++;            swap(arr[i], arr[j]);  // 把小的数换到左边        }    }    swap(arr[i + 1], arr[high]);  // 把基准放到正确位置        // 递归排序左右两部分    quick_sort(arr, low, i);      // 排序左边    quick_sort(arr, i + 2, high); // 排序右边}int main(){		vector<int> array ={38, 27, 43, 3, 9, 82, 10};	quick_sort(array,0,array.size()-1);		for (int num : array) {        std::cout << num << " ";    }	}

总结：分治法的核心是“分而治之”：通过递归分解问题→解决子问题→合并结果，将复杂问题化繁为简。

典型代表：快速排序、归并排序。

Tags：

猜你喜欢

最近发表
标签列表