纺织品服装网站建设优化,o2o网站,网站建设岗位职责怎么写,电商网站开发计划分治思想#xff0c;分治策略#xff0c;自古有之#xff0c;与人类生活息息相关#xff0c;其本质是将大问题拆解为小问题#xff0c;小问题转换为已知解的问题#xff0c;进而求解。
军队管理#xff0c;国家分级治理…… 大规模数据排序#xff0c;例如10000000000…分治思想分治策略自古有之与人类生活息息相关其本质是将大问题拆解为小问题小问题转换为已知解的问题进而求解。
军队管理国家分级治理…… 大规模数据排序例如10000000000万个数规模大的时候分治思想就很重要了。
基本思想
分如果问题还大就再分直到其变成容易求解的基本问题这个过程其实与递归的类似的。 总而言之递归思想与分治策略有着密不可分的联系。
对于分解之后的基本问题我们就可以使用一些基本的策略求解因为容易比如枚举。 核心策略
分大问题– 小问题 -- 基本问题治解决基本问题合将基本问题的解合并得到原问题的解 抽象的理论内容很重要我们把握其核心思想和本质但是想要理解抽象我们更应该解决实际问题在实际问题中理解抽象概念达到融会贯通。
基本框架程序 理解问题分解问题找到自己认识的部分或者从最简单情况出发递推地分析一下获得简单问题的求解办法将大问题递归地分解为简单问题去处理将每个小问题的解合并
如此抽象说了也白说直接上例子。
归并排序
最难点【合】的策略合无定法 分治策略与递归的对应关系
分进行递归操作 治递归终止条件和处理办法 合递归处理办法
对于归并排序
分将数组不断进行二分直到其剩余1个元素治对于1个元素一定是有序的就可以将其作为基本问题的解返回合对于基本问题的解需要让其合并后有序因此合并需要专门的一些策略针对归并排序特点进行设计。
合是最难的因为合无定法每种问题的每种解法可能都不一样。
看代码
#include ctime
#include iostream
using namespace std;// 给你一个规模很小的数组并且告诉你分两半每一半都是有序的让你给合起来依然有序
// 合
void merge(int data[], int buffer[], int min, int mid, int max) {int first_mid_pointer min; // data[min, mid]int second_mid_pointer mid 1; // data[mid1, max]int buffer_pointer min; // buffer[min, max]while (first_mid_pointer mid second_mid_pointer max) {if (data[first_mid_pointer] data[second_mid_pointer]) {buffer[buffer_pointer] data[first_mid_pointer];buffer_pointer;first_mid_pointer;}else{buffer[buffer_pointer] data[second_mid_pointer];}}// 传递剩余部分if (first_mid_pointer mid) {while (first_mid_pointer mid buffer_pointer max) {buffer[buffer_pointer] data[first_mid_pointer];}} else {while (second_mid_pointer max buffer_pointer max) {buffer[buffer_pointer] data[second_mid_pointer];}}}// 归并排序
void merge_sort(int data[], int buffer[], int min, int max) {// 治if (min max)return;if (min max){// 分int mid (max min) / 2; // ;not -merge_sort(data, buffer, min, mid);merge_sort(data, buffer, mid 1, max);// 合“治”之后才会执行merge(data, buffer, min, mid, max);// buffer result -- datafor (int i min; i max; i) { // 注意起点和终点注意“”data[i] buffer[i];}}
}int main()
{clock_t start, end;for (int n 64; ; n * 2) {// initializationint *a new int[n];for (int i 0; i n; i) {a[i] rand() % 10000 1;}// merge sortstart clock();int length n; //sizeof(a) / sizeof(a[0]);int *buffer new int[length];merge_sort(a, buffer, 0, length - 1);end clock();cout N n time end - start endl;if ((end - start)*2 180000) // predict: more than 3 minutes,stop!break;}return 0;}类似版本的代码
#include iostream
using namespace std;// combine function
// data sequence: min to max
void combine(int data[], int buffer[], int min, int mid, int max) {// NOTE: max length of array - 1int before_mid_pointer min; // data[min,mid]int after_mid_pointer mid 1; // data[mid1,max]int buffer_pointer min; // buffer[min,max]while (before_mid_pointer mid after_mid_pointer max){if (data[before_mid_pointer] data[after_mid_pointer])buffer[buffer_pointer] data[before_mid_pointer];elsebuffer[buffer_pointer] data[after_mid_pointer];}// process the rest of data that is not be compared// add them to buffer directlywhile (before_mid_pointer mid buffer_pointer max){buffer[buffer_pointer] data[before_mid_pointer];}while (after_mid_pointer max buffer_pointer max){buffer[buffer_pointer] data[after_mid_pointer];}// add buffer to datafor (int i min; i max; i) {data[i] buffer[i];}}// 自始至终我们都是使用一个data和一个buffer通过指针值“虚拟地”分割和排序。
// merge sort
void merge_sort(int data[], int buffer[], int min, int max) {if (max min) {// divideint mid (max min) / 2;merge_sort(data, buffer, min, mid);merge_sort(data, buffer, mid 1, max);// combine: sort two sorted arrays using specified methodcombine(data, buffer, min, mid, max);} else {// conquer: only 1 elementreturn;}
}int main() {int data[8] { 1,3,5,0,100,4,33,7 };int buffer[8] { 0 };merge_sort(data, buffer, 0, 7);for (int i 0; i 8; i) {cout buffer[i] ;}return 0;
}小结
分治思想用一个成语就是庖丁解牛完整的牛我们搞不懂就将其合理地拆解分成小部分然后就可以搞定了。
还需要大量实例去体会分、治、合的思想策略。
我们知道了分治策略与递归思想的结合。
治理的是基本问题也就是递归的结束条件和结束时候的处理办法。
而分则是递归调用过程它指明了我们应该如何调用递归函数去分割问题使其更简化。
最后合则是在某个递归函数返回之后的处理办法它也在递归处理过程内只有递归返回后才会执行用于合并返回的基本问题的解从而得到最终的复杂问题的解。
对于归并排序我们有一个比较神奇的点那就是自始至终data和buffer都使用的是一个而所谓的分割都是通过虚拟的指针来实现的我们并没有真地将其分割
算法学习策略
原理与思想本质实例与图解实际问题分析 抽象实现
需要这几个过程才能真正体会算法思想的精髓通过大量实例和图解能够更好地理解算法理解思想本质。
