分治算法思想是将一个问题分拆为多个子问题，解决子问题（在递归最底层解决），并合并结果。分治算法的复杂度有三个因素影响，a、b、d；分拆成a个子问题，每个子问题规模为1/b，合并或分拆的开销为O(n^d)：判断d~log_b^a大小，前者大的时候，d是决定性因素；相等，则复杂度为nlogn；小于，则ab是决定性因素。
经典的分支算法是合并排序：将一个长度为n的数组排序，将其分拆为两个等长的子数组排好序之后合并。两个子问题没有重叠，即“a=b。”又合并复杂度为O(n)。故总复杂度为O(nlogn)。树上有证明这是最优的bound。
另一问题是寻找中项（或者第k项）：寻找一个乱序数组的第k大的项。与merge排序的区别在于中项寻找算法先对无序数组有序划分，然后递归再合并的时候就方便了。而merger算法是做无序划分，合并的时候复杂度为O(n)。
快速排序是两者的结合；排序算法但进行有序划分。
快排VS归并排序
优势：无额外空间（适合大文件排序），移动次数少（适合小数据类型，如整数数组排序）
劣势：比较次数多（不适合Object排序，其比较操作耗时）
快排实现：在递归的底层（如长度只为10的小数组），不要用快排，直接用冒泡（生成随机数费时）
乘法的计算：大整数的乘法，矩阵乘法和多项式乘法。整数前n/2位和后n/2位，矩阵则为四个象限。多项式的乘法介绍如下：
多项式乘法（或者说矢量之间卷积）在信号与系统中有应用（如对时不变线性系统，第d+1时刻的信号（多项式函数）值是前d个时刻该多项式值与对应脉冲多项式的乘积；也可以计算大整数乘法）FFT傅立叶变换是解决这个问题的方法。具体如下：
多项式本身有系数表示和值表示两种，用值表示的时候乘法可以O(n)下完成。计算思路是把系数表示转换为值表示，做乘法，再转回来。核心问题是如何做转换，描述如下：
“多项式f(x)=a_(n-1)*x^(n-1)+...a_1*x+a_0求x=x_0,x_1,...x_(n-1)值。” 本质上这是一个矢量和矩阵乘法的问题（[f(x)]=M(x)*[a_0,...a_(n-1)], M矩阵见书），技巧之处在于如何选择n个x值，使得计算能够简化。思路如下：
使用1的n次方根w作为x，使得系统能够递归调用。详细见书！（矩阵能分拆成四个小矩阵，其中两个是重复的。）
1 条评论:
There are two choices in designing a divide-and-conquer algorithm, that is, top-down manner and bottom-up manner.
The merge sort and order statics (see CLRS) is typical in bottom-up manner.
In this category, the analysis of complexity could be a bit different (though the general equation still applies.) For example, the merge sort is O(NlogN), while the order statistics could be O(N). A key observation is whether data magnitude is reduced (or some data is pruned out) in the bottom-up process.
The bottom-up manner is naturally suitable to resolve some problem. For example, "knowing that an element appears in an array in more than n/2 times, how could you find this element?"
发表评论