算法即计算的方法，使用计算的思想、方法、工具和技术来实现问题求解的思路和途径。计算机提供了计算的能力和硬件设施；算法则提供了计算的思想和软件技术，更好地发挥计算机的潜能。
有人说，算法无用，这种观点就如同盲人看不到花开就说世界上没有花一样，是一个长眼睛的人无论如何也难以接受的
现在，就让我们来梳理一下常用的算法设计技术吧！
一、 分治法：将问题实例 P(n) 分解为 b 个子问题实例 P(n/b) ， 其中有 a 个子问题需要求解。 然后将子问题的解合并起来得到原问题的解。
一言以蔽之， 即“分而合之”。
例子：
① 归并排序： 将待排序列表先分成若干的子列表，分别排序，然后合并起来
——归并排序的关键在于“合”的过程；
② 快速排序： 选取列表中的某种元素，放在列表中的某个位置，使列表分为小于该元素和不小于该元素的两个子列表。
然后，分别对两个子列表重复上述步骤，直到整个列表有序为止。
——快速排序法 关键在“分”的过程。
③ 二叉树遍历： 分别遍历根结点、左子树和右子树。
——具有天然的分治和递归特性。
分治法的效率：
T(n) = aT(n/b) + f(n) , 其中 f(n) 是“分”或者“合”的过程中所耗费的时间。
对于归并排序来说， f(n) 是将两个有序列表合并成一个更大的有序列表所耗费的时间；对于快速排序来说， f(n) 是选取分割元素并将其放在最终位置所耗费的时间。
根据主定理： 令 f(n) = O(n^d),
① 当 d > log(a)/log(b) 时， T(n) = n^d;
② 当 d = log(a)/log(b) 时， T(n) = (n^d)log(n)
③ 当 d < log(a)/log(b) 时， T(n) = n^(log(a)/log(b))
主定理其实很好记： T(n) 的效率由 aT(n/b) 和 f(n) 的效率比较而得，其中 aT(n/b) 的效率可看成： n^(log(a)/log(b))，只要比较幂数取大者就可以了。
常用的分治法，是将问题实例分成规模大致相等的2个子问题实例。
根据主定理：
T(n) = 2T(n/2) + O(C) , C 是常数 --------- T(n) = O(n)
T(n) = 2T(n/2) + n ----- T(n) = O(nlog2(n))
T(n) = 2T(n/2) + n^2 ------------------- T(n) = O(n^2)
可以看出， f(n) 也是起很重要作用的， f(n) 不能太大， 最好是线性的，否则， 采用分治法的效率就可能不高了。合理采用分治法的效率一般应该可以达到O(nlog2(n))，至少应该比采取其他算法技术的效率要高一个级别。
蓝鸥科技西安中心，移动互联网科技育人专家，教育部产学合作协同育人项目承办企业，专注西安Java培训、西安大数据培训、西安unity培训，西安VR/AR培训、西安UI设计，西安HTML5培训、西安PHP培训，选择蓝鸥，不止高薪更是高起点！
898995850
