选择问题：
前提问题：数组中的中位数距离其他数字的距离最小

问题一：选取数组的最大和最小的值
常规方法：比较W(n)= n-1+n-2=2n-3
分治法：两两分组，每一组选出大元素和小元素，此时数组分成两部分，分别进行取极值

W(n)=

问题二：取第二大的值
常规方法：W(n)=n-1+n-2=2n-3
锦标赛法：两两分组，选出最大的元素进入下一轮，下一轮中两两分组选出最大的值，直到产生冠军。比较(n-1)次。
又因为第二大元素必是被冠军淘汰，所以在比较的同时需记录被其淘汰的元素。在被冠军淘汰的元素中选出最大值，即第二大元素。

其W(n)=

其中向上取整logn-1：
被冠军淘汰的元素数量=轮数
因为每一轮淘汰n/2个元素，即有n/(2^h)=1 解得h=logn所以比较此时logn-1

问题三：取k小的元素
一般法：排序O（n*logn）

Select(S,k)
步骤一：首先将数字分为5个一组，一共向上取证n/5组
步骤二：每一组选择其中位数【消耗O(n)】
步骤三：将每组的中位数从大到小排序，可以得到众多中位数的中位数M【W(n/5)】，其可以将所有数字分成四组。可以看出B,C分区的数字一定大于M，AD的数字无法和M直接判断。
步骤四：将A,D依次和M进行比较，将较小的数字放入C中得到S1，较大的数字放入B中得到S2。【若假设A,D都小于M，则转化为子问题W【7n/10】】
步骤五：若k=|S1|+1,输出M；若k<|S1|+1，则Select(S1,k)；若k>|S1|+1，则Select(S2,k-|S1|-1)

假设数字总数n=10r+5，则分区后：
A=D=2r，B=C=3r+2
若假设A,D都小于M，则转化为子问题W【7n/10】
则得到递归公式：

利用递归树得到右方表达式的和，得到

注意结论：即将问题划分为规模较小的子问题


当为3个一组时：
假设总个数为n=6r+3，从子分区中找到各自的中位数O(n)，从所有中位数中找到中位数M【W(n/3)】则分区的个数A=D=n，B=C=2n+1。同样假设A,D全小于M，
则A+D+C=4n+1<4n+2=W(2n/3)
所以W(n)<W(n/3)+W(2n/3)+O(n) 得到W(n)= O(nlogn)
没有显著降低时间复杂度，原因在于 c+d不小于1.
当为7个一组时：按上图分析方法

卷积简介

卷积的应用：信号平滑处理

对于信号向量a=(a0,a1,a2-----,am-1)
我们新增向量b=(b2k,b2k-1,-----b0)等价于(w-k,w-k+1,------wk-1,wk)
则对于每个向量ai，对其进行ai*bj的平滑处理（其中i+j=2k+i-2）
如图，蓝色为向量b固定，黄色为向量a在向量b上移动。

举个例子：对a2进行信号处理，则将a2’=a0b2k+a1b2k-1+a2b2k-2+a3b2k-3+a4*b2k-4
可以看见同一个ai’中 a,b的的下标和为定值
误差在于：两边的值无法完全对应，可能存在误差。如本图中，a0’,a1’,a7’a8’存在误差

如何进行卷积运算

要求：求得向量 a=(a 0 ,a 1 ,…,a n-1 ) 和b=(b 0 ,b 1 ,…,b n-1 )的卷积结果c
方法1：蛮力运算
将向量扩充为多项式A(x),B(x)
则AB=C,C的系数向量就是ab

方法二：多项式插值法
原理：如对于2n-2次方程，需要2n个点值即可求解
1：首先x0,_x2n-1是2n个不同的值，当带入到A(x),B(x)时可以得到
A={(x0,A(x0) ,(x1,A(x1))-----------(x2n,A(x2n))}等点值对，同理B
2：计算C(x0)=A(x0)*B(x0)可以得到2n个C(xi)值
C={(x0,C(x0) ,(x1,C(x1))-----------(x2n,C(x2n))}
因为C是一个2n-2次方程，所以2n个点值可以通过多项式插值解得其系数

如何选取好的x0,x1----------x2n-1呢？

下图为欧拉公式


通过上述图片，我们可以得出【如何选取好的x0,x1----------x2n-1呢？】的结果，即选取1的2n次方根来充当x.
所以当选取1的根号2n次方根时间，成为FFT变换：

多项式求值算法

题目：对于x^n-1次方的多项式A(x)，当x为1的2n次方根时【有2n个值】，如何求得A【同样2n个结果】的值？
方法一：依次带入计算
对于xi：计算 1+2+ -----x-1(n-1次乘法) O（n^2）
因为有2n个xi，所以时间复杂度O(N^3)

方法二：Ai(x)看做是中间值辅助变量，用于计算Ai+1（x）

方法三：分治法：
即将A（x）分为两个子问题，Aeven(x^2)和Aodd(x ^2)

此方法的时间复杂度为：

平面点集的凸包：

解答：
首先由集合Q，从集合Q中找到最大纵坐标点 y max 和最小纵坐标点 y min 的线段d={y max ,y min }划分L 集为左点集 L(left) 和右点集 L(right)
执行D(left),D(right)
其中
D(left):d=left
1:找到距离d最远的点P，构成三角形
2:另两条边记为a,b.于是Q中在三角形中的点删去
3:D(a)//此为递归调用
4:D(b)//此为递归调用

时间复杂度分析：