《趣学算法》学习打卡Day 4！

分治法

1、山高皇帝远

”凡治众如治寡，分数是也。“——《孙子兵法》

将一个大规模的问题分解成若干个规模较小的相同子问题，分为治之。

分治的基本条件：

1. 原问题可以分解成若干个规模较小的相同子问题。
2. 子问题相互独立。
3. 子问题的解可以合并为原问题的解。

2、猜数游戏——二分搜索技术

顾名思义：二分查找，折半查找策略

3、合久必分，分久必合——合并排序

一个数组集合有n个元素时，元素间会相对无序，但是对于一个元素来说，本身有序，所以把数组拆分成单个的元素，在从元素组成原来的数组；

见图：

4、兵贵神速——快速排序

快速排序耗费时间最小，与合并排序恰好相反，怎样把数据元素分开是快速排序的难点，属于”先苦后甜“型。

找一个基准元素，把小于等于基准元素的放在左边，大于基准元素的放在右边。分解成两个子序列，对两个子序列进行快速排序，直到子数列为有序。

5、效率至上——大整数乘法

大数据相乘的时候硬件不支持，则需要将其分解成若干个小问题，通过小问题的求解再组合成原问题的解；不仅可以改善计算机硬件的不支持性，又可以提高计算效率。

大数：一般就是指用字符串来储存数字，然后设计程序完成加减乘除运算！

6、分治算法复杂度求解秘籍

1. 递归树求解法

   就是和高中求通项公式一样

2. 大师解法