分治算法

分治算法补充内容：

●最大子数组问题：

将S1和S2加起来得到S3，看S1、S2、S3中谁最大就取谁的值当做Smax。一步步计算出S1、S2和跨S1、S2中心的S3，比较谁大当做Smax再接着往下走：
计算得到T(n)=O(nlogn).
最小子数组的问题各种求解算法比较：

●逆序对计数问题：
S3的求解最佳方法是：归并排序
在合并的同时一边对子数组各元素进行排序使之成为有序数组，一边对右边的数组每个元素求与左边数组对应的逆序对！！这样求解S3的时间复杂度就降至O(n)了。





求解逆序对数目各算法比较：

小结排序算法：

归并排序的应用之一是：逆序计数
（写在最后：本文图片均来自中国大学MOOC北航课程PPT，链接：https://www.icourse163.org/learn/BUAA-1449777166?tid=1450250462#/learn/content）