进一步认识分治算法(二)

时间：2022-01-28 09:41:07

    为了进一步了解和掌握分治算法，请各位看官，继续往下打量。主要涉及的问题有选择类问题(选第k小，选第二大，选最值等)、信号平滑处理问题(卷积应用，卷积计算，快速傅里叶FFT变换)、计算平面点集的凸包、二份查找、快速排序、二分归并排序。

    

例1：选最大的数

基本运算是比较

蛮力算法：比较n-1次


例2：同时选择最大和最小

基本运算是比较

蛮力算法：先选最大，n-1次比较；再选最小，n-2次比较，总共比较2n-3次

分治算法:

  • 分解均分数组L为L1和L2
  • 分治递归地球L1的最大max1和最小值min1
  • 分治递归地球L2的最大max2和最小值min2
  • 合并max = max{max1,max2}
  • 合并min={min1,min2}

时间复杂度：W(n)=2W(n/2)+2,W(2)=1,设n=2^k，迭代求得W(n)=3n/2-2，优于2n-3次


例3：选第二大

基本运算是比较

蛮力算法：先选最大n-1次，再选次大n-2次，和之：W(n)=2n-3

锦标赛算法：

  1. n(记为k)个元素两两分组，分成n/2下取整组
  2. 每组2个数比较，找到较大数
  3. 将被淘汰(较小)的数记入较大数的链表
  4. If k是 奇数，then本组有n/2下取整+1(记为k)个元素
  5. else 本组有n/2(记为k)个元素
  6. if k >1 then goto 1
  7. else 得到max
  8. 取max链表中的最大者 

看实例：

    进一步认识分治算法(二)

时间复杂度分析：

    算法中可以看到，n个元素，经过i轮分组并淘汰后元素剩余至多为n/(2^i)的上取整。还有，n个元素中为了求出max，总计进行了logn上取整次分组淘汰。那么n个元素中为了求出max，比较运算有多少次，我想不难计算，有logn上取整次分组，把每组的比较次数加起来，则有n/2+n/(2^2) +n/(2^3)+…+n/(2^k), 当n为偶数，则n/(2^k)=1，k=lgn，这个加法式子中有lgn项，不难用等比求和公式算之，可得n-1，当n为奇数亦可得n-1，所以n个元素中为了求出max，比较运算有n-1次。

    根据算法接下来在max的链表中找最大，不难看出max的链表中有logn上取整个元素，因为每次分组max都会有一次比较，最后剩余max时，max与其他元素比较了logn上取整次，也就淘汰了logn上取整个值，全都记在它的链表中。把它的链表再用同样的竞赛淘汰算法求出max即可，这次的元素有logn上取整个，那么同理会比较logn上取整减1次。故为了求出第二大所付出的时间复杂度为W(n)= n-1+ logn上取整-1= n+ logn上取整-2

一般性选择问题的算法设计与分析

    算法一：调用k次选最小算法，O(kn)

    算法二：先排序，然后输出第k小，最好的排序复杂度O(nlogn)

    分治算法：

  1. 用某个元素m*作为划分标准，将S集合划分成S1，S2，其中S1中的数小于m，S2中的元素大于m*
  2. If  k<= |S1|，则在S1中找第k小；if k=|S1|+1，则m就是第k小；ifk>|S1|+1，则在S2中找k-|S1|-1小

    说明：算法效率取决于子问题的规模，可以通过选取m来控制子问题的规模。

    一种划分过程如下图：

进一步认识分治算法(二)

    1.先把数分成n/5下取整个组，2.每组从大到小排序，3.每组取中位数组成M数组，4.把M以中位数为基准划分成左边数小于中位数，右边都大于，则此时有以下区域划分：

进一步认识分治算法(二)

    图中，A：需要和m*比大小，B：数大于m*，C：数小于m*，D：数需要与m*比大小，其中A和D中的数和m*比较大小后，大的划入B，小的划入C，至此，本次划分完毕。

    这种划分一个实例：

    进一步认识分治算法(二)进一步认识分治算法(二)

    具有这种划分的算法的伪码：

    输入：数组S，k

    输出：S中的第k小元素

    Select(S,k)

  1. 将S 中元素5个一组，共有n/5上取整个组
  2. 每组从大到小排序
  3. 每组取中位数组成M数组，把M以中位数为基准划分成左边数小于中位数，右边都大于
  4. m*是M数组的中位数，使用Select(M, |M|/2上取整)这个子问题算得
  5. A，D中元素小于m*放入S1，大于放入S2
  6. S1=S1∪C，S2= S2∪B
  7. If  k=|S1|+1，then 输出第k小m*
  8. else if  k<= |S1|，then Select(S1,k)
  9. else Select(S2,k-|S1|-1)

    说明：中位数的概念不是中间的数，而是数组中第|M|/2上取整小的数

    思考：从划分图形上来看，有一维的数组划分，有二维的数组划分，有没有三维的数组划分呢？有兴趣的看官、老板可以试一试。甚至多维的。

    

一般性选择问题分治算法的时间复杂度分析

     这一节，你会看到上一节中的分治算法在不同划分中的最坏情况下的时间复杂度分析，时间复杂度有什么用？这一节能告诉你，你自己编写的以为高效率的算法，可能并不是那么高效，高不高效，我们还是拿时间复杂度这个概念来科学衡量吧，堪称是经典。

    以下考虑算法最坏复杂度的情况。我们知道在划分规则已知的前提下，划分的子问题规模越大，那么复杂度也就越高了。上一节的分治算法里有三个子问题的划分，他们的输入规模分别是：

  1. 划分成的M数集的元素个数；
  2. 划分成的S1数集的元素个数；
  3. 划分成的S2数集的元素个数

    另外，若设总的时间复杂度为W(n)，处理输入是M的子问题的时间复杂度为M(n1)，类似地设S1(n2)，S2(n3)，其他耗费的时间复杂度为Other(n4)，那么我们有：

W(n)= M(n1)+ S1(n2)+S2(n3)+ Other(n4)

    *_*，对吗？此时我们要清楚地知道，算法在处理以S1和以S2中作为输入的子问题时，是根据条件做了选择，并不是并行地处理了这2个子问题，上面的式子中显然是人为地做了并行计算，所以只有：

W(n)= M(n1)+ (S1(n2)or S2(n3))+ Other(n4)

    好了，现在，我们知道在划分规则已知的前提下，M的规模是个常数。所以把目光聚焦到S1和S2的规模上，我们设初始的原问题总的规模为n=5(2r+1)，按照我们的算法，则会出现以下如图划分：

    进一步认识分治算法(二)

    划分共有2r+1列，且|A|=|D|=2r，且S1=A、D中小于m*的元素∪C，S2= A、D中大于m*的元素∪B。为使得子规模赠大，只要增加S1和S2的元素就行，为使得W(n)最大，我们可以这样做，每次递归都选择其中一个具有最大规模的子问题，而子问题的最大规模可以是|A|∪|D|∪|B|，也可以是|A|∪|D|∪|C|，因为本划分的|B|=|C|，当然有的划分|B|!=|C|，即问题的规模为2r+2r+3r+2=7r+2，由n=5(2r+1)得r=n/10-1/2，从而子问题规模7r+2=7n/10-3/2<7n/10，此时W(n)由以下工作量组成：

  • M数集的组合：O(n)
  • 找M数集的中位数: W(n/5)
  • 划分S1和S2，只要是比较A，D数集中的元素：O(n)
  • 子问题：不超过W (7n/10)
  • 所以有：W(n)<=W(n/5)+W(7n/10)+O(n)，可以用递归树求其渐进解：
     进一步认识分治算法(二)

    孤芳自赏的你我可能为认识了这个算法都很开心，然后戛然而止。可是我就知道有那么一些有精力，有抱负，有理想，有秩序的老板、看官会保留一些疑问压箱底，为什么一开始就要把5个元素一组的划分？不能是其他的奇数个元素一组吗？好吧，严肃的追问往往都是一记记响彻长空的耳光。

    好吧，分析一下，根据W(n)=M(n1)+ (S1(n2) or S2(n3))+ Other(n4)，设t是分组的元素个数，则：

  • 看M(n1)，n1=n/t，t愈大，n1愈小，M(n1) 愈小，反之M(n1)愈大。
  • 而考虑S1(n2) or S2(n3)，t愈大，n2，n3愈大，为什么？下面的2个图形只是说明n2,n3不仅与t有关，还和n总规模有关。

    关于2.我们设t是奇数，则子问题的最大规模有：n2=n3=f(n,t)=[2(n-t)+(t-1)(3n-t)]/4t，这个f(n,t)的值实际还和n总规模有关系，并不是“t愈大，n2，n3愈大”，当n=1000时的函数图像：

进一步认识分治算法(二)

    t =31时，f(1000,31) ~734取得子规模的最大值，当t>31，t取的愈来愈大时，子规模在减小，S1(n2) or S2(n3)也是在减小，M(n1)也在减小，Other(n4)的消耗在增大，但是Other(n4)还是O(n)。当n=100时的图像形态大致一样，t =10时，f(100,10)~ 70取得子规模的最大值，10之后n1,n2,n3减小。

进一步认识分治算法(二)

    总结以上总的时间复杂度为：W(n)=W(n/t)+W(f(t))+cn，使用递归树可以推得，当n/t+f(n,t)-f(0,t)<n时，可使得W(n)=O(n),若n/t+f(t)-f(0,t)>=n，W(n)=O(nlgn)，例如：当t=3时， h(n)=n/t+f(t)-f(0,t)-n=0,故W(n)=W(n/3)+W(2n/3)+cn=O(nlgn)，当t>3时, h(n)<0,得W(n)=O(n)

    以上都是求解渐进的上界，也就是求最坏的时间复杂度，也是一个渐进的解，并不是精确的运算次数。

例4：计算几何里计算凸包的例子，略。

例5：快速排序，略，相当于二叉树前序遍历，若数集是用链表组织，快速排序跑起来会很喘，适用于数据量大的线性结构，数量在成百上千甚至万级

例6：归并排序，略，相当于二叉树后序遍历，适用于数据量大链式存储或者线性存储，数量在成百上千甚至万级

例7：汉诺塔，略，相当于二叉树中序遍历

例8：二分查找，实现简单，下面是他的迭代实现：

         binarySearch([] arr,startindex,endindex,key){

                   int low=startindex;

                   int hight=endindex-1;

                   while(low<=hight){

                            intmid = (low+hight)/2;

                            intmidValue = arr[mid];

                            if(key>midValue){

                                     low= mid+1;

                            }elseif(key< midValue){

                                     Hight=mid-1;

                            } else{

                                     Returnmid;

                            }

                }

         }

转载请注明出处。

参考：

    https://www.bilibili.com/video/av7134874/?from=search&seid=14261249226249986779
标签：

相关文章