精华内容
下载资源
问答
  • 计算时间复杂度分治法与递归) 本文为转载,原链接忘记了 分治法的道理非常简单,就是把一个大的复杂的问题分为a(a>1)个形式相同的子问题,这些子问题的规模为n/b,如果分解或者合并的复杂度为f(n),那么总的...

    计算时间复杂度(分治法与递归)

    本文为转载,原链接忘记了
    分治法的道理非常简单,就是把一个大的复杂的问题分为a(a>1)个形式相同的子问题,这些子问题的规模为n/b,如果分解或者合并的复杂度为f(n),那么总的时间复杂度可以表示为:
    在这里插入图片描述

    1.递推求解法 我们上面的求解方式都是递推求解,写出其递推式,最后求出结果。 例如:合并排序算法的时间复杂度递推求解:
    在这里插入图片描述

    2.递归树求解法 递归树求解方式其实和递推求解一样,只是递归树更清楚直观的显示出来,更能够形象的表达每层分解的结点和每层产生的成本有多少。例如:
    在这里插入图片描述

    在这里插入图片描述

    3.大师解法
    在这里插入图片描述

    递归树
    在这里插入图片描述

    时间复杂度=叶子数*T(1)+成本和
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    例子:
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    首先从递归树中观察每层产生的成本发展趋势,每层的成本有时不是那么有规律,需要仔细验证才行。比如我们得到第3层是(5/16)2n2,需要验证第4层是(5/16)3n2,…。经过验证,我们发现每层成本是一个等比数列,公比为5/16<1,呈递减趋势,那么只需要计算第一项即可。时间复杂度:T(n)=O(n2)

    展开全文
  • 分治法的递归算法时间复杂度分析

    千次阅读 2015-01-22 17:27:35
    最近看分治法,那我们就一起研究下分治法的时间复杂度吧。 分治法是将问题分解为语言问题等价的规模相等的子问题进行求解的过程。因此根据定义可知,如果原问题为A该问题被分解为K个子问题,则子问题应该为A/k。...

    最近看分治法,那我们就一起研究下分治法的时间复杂度吧。

    分治法是将问题分解为语言问题等价的规模相等的子问题进行求解的过程。因此根据定义可知,如果原问题为A该问题被分解为K个子问题,则子问题应该为A/k。同时当子问题被解决之后,对子问题还应该有一个合并的过程,让子问题被重新归纳为原问题。规范的描述过程应该是:

    1、原问题为A

    2、划分子问题A/k

    3、解决子问题

    4、归并子问题

    设解决子问题被解决需要的时间复杂度为O(1),归并规模为n的子问题需要的时间复杂度为f(n),则该过程的时间复杂度应该可以使用递归公式T(A) = T(A/k) + f(n)

    T(A) - kT(A/k) = f(A)          (1)式
    T(A/k) - kT(A/k*k) = f(A/2) (2)式

    (1)式 + k(2)式 可得:
     T(A) + k*k*T(A/k*K) = f(A) + k*f(A/2)


    重复该过程可知: T(A) -  power(K,logk A) * T(1) = [1,k,k*k,...... power(K,logk A)-1]*([f(A), f(A/k),......f(A/power(K,logk A)-1]的转置矩阵)

    因为设f(A) = O(A)则K* f(A/k) = k * O(A/k) = O(A)

    T(A) =  A * T(1)  + (logk A)O(A)

    将T(1)得复杂度代入即可得到具体的总体时间复杂度值。


    展开全文
  • 递归算法时间复杂度

    2013-04-26 10:40:47
    在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?...

    开篇前言:为什么写这篇文章?笔者目前在学习各种各样的算法,在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?在google过很多的博文后,感觉这些博文总结的方法,有很好优秀的地方,但是都不够全面,有感于此,笔者决定总结各家之长,作此博文,总结各种方法于此,有不足之处,欢迎各位批评指证!

      在算法的分析中,当一个算法中包含递归调用时,其时间复杂度的分析会转化成为一个递归方程的求解。而对递归方程的求解,方法多种多样,不一而足。本文主要介绍目前主流的方法:代入法,迭代法,公式法,母函数法,差分方程法。


       【代入法】代入法首先要对这个问题的时间复杂度做出预测,然后将预测带入原来的递归方程,如果没有出现矛盾,则是可能的解,最后用数学归纳法证明。

      【举   例】我们有如下的递归问题:T(n)=4T(n/2)+O(n),我们首先预测时间复杂度为O(n2),不妨设T(n)=kn2(其中k为常数),将该结果带入方程中可得:左=kn2,右=4k(n/2)2+O(n)=kn2+O(n),由于n2的阶高于n的阶,因而左右两边是相等的,接下来用数学归纳法进行验证即可。


       【迭代法】迭代法就是迭代的展开方程的右边,直到没有可以迭代的项为止,这时通过对右边的和进行估算来估计方程的解。比较适用于分治问题的求解,为方便讨论起见,给出其递归方程的一般形式:

      【举   例】下面我们以一个简单的例子来说明:T(n)=2T(n/2)+n2,迭代过程如下:

      容易知道,直到n/2^(i+1)=1时,递归过程结束,这时我们计算如下:

      到这里我们知道该算法的时间复杂度为O(n2),上面的计算中,我们可以直接使用无穷等比数列的公式,不用考虑项数i的约束,实际上这两种方法计算的结果是完全等价的,有兴趣的同学可以自行验证。


      【公式法】这个方法针对形如:T(n) = aT(n/b) + f(n)的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系,即一个规模为n的问题被分成规模均为n/b的a个子问题,递归地求解这a个子问题,然后通过对这a个子问题的解的综合,得到原问题的解。这种方法是对于分治问题最好的解法,我们先给出如下的公式:

      公式记忆:我们实际上是比较n^logba和f(n)的阶,如果他们不等,那么T(n)取他们中的较大者,如果他们的阶相等,那么我们就将他们的任意一个乘以logn就可以了。按照这个公式,我们可以计算【迭代法】中提到的例子:O(f(n))=O(n2),容易计算另外一个的阶是O(n),他们不等,所以取较大的阶O(n2)。太简单了,不是吗?

      需要注意:上面的公式并不包含所有的情况,比如第一种和第二种情况之间并不包含下面这种情况:f(n)是小于前者,但是并不是多项式的小于前者。同样后两种的情况也并不包含所有的情况。为了好理解与运用的情况下,笔者将公式表述成如上的情况,但是并不是很严谨,关于该公式的严密讨论,请看这里。但是公式的不包含的情况,我们很少很少碰到,上面的公式适用范围很广泛的。

      特别地,对于我们经常碰到的,当f(n)=0时,我们有:


      【母函数法】母函数是用于对应于一个无穷序列的幂级数。这里我们解决的递归问题是形如:T(n)=c1T(n-1)+c2T(n-2)+c3T(n-3)+...+ckT(n-k)+f(n)。为说明问题简便起见,我们选择斐波那契数列的时间复杂度作为例子进行讨论。

      【举  例】斐波那契数列递归公式:T(n)=T(n-1)+T(n-2)。这里我们假设F(n)为第n项的运算量。则容易得到:F(n)=F(n-1)+F(n-2),其中F(1)=F(2)=1.我们构造如下的母函数:G(x)=F(1)x+F(2)x2+F(3)x3+......,我们可以推导如下:

      上面的方法计算相对来说是比较简单的,关键在于对于母函数的理解,刚开始的时候可能不是很好理解,对于母函数可以参考这里维基百科这里


      【差分方程法】可以将某些递归方程看成差分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近阶估计。这里我们只考虑最长常见的递归形式,形如:T(n)=c1T(n-1)+c2T(n-2)+c3T(n-3)+...+ckT(n-k)+f(n),其中c1,c2,...ck为常数且不等于0;我们对该方程的求解如下:

      对应上面的齐次方程的特征方程为:

      如果解得t=r是该特征方程的m重根,则这m个解的形式为:{rn     n*rn      n2rn   ...    nm-1rn},其余的关于复数解的形式和普通的线性方程组的形式类似,不再赘述。接下来,我们要求解该方程的对应非齐次方程组的通解,这里我们针对该方程的特殊形式,不加证明地给出如下的通解形式:

      则和线性代数中的解一样,原方程的解等于齐次方程组的通解+特解,即:

      最后由初始条件确定a(i)的值即可。

      为了帮助理解,我们举两个例子看看,就明白是怎么回事了。

      【举 例1】递归方程如下:

    (1)写出对应齐次方程的特征方程:

    得到基础解系为:{t1n,  t2n}

    (2)计算特解,对于本题,直接观察得特解为:-8

    (3)得到原方程解的形式为:T(n)=a0t1n+a1t2n-8

    (4)代入n=0,n=1的情况,得到a0,a1,最后可得:

      可以看到该方程形式和上面讨论过的斐波那契数列只差一个常数8,因而两者的时间复杂度是相同的。有兴趣的同学可以按照这个方法再次计算斐波那契数列的时间复杂度验证一下。

      【举  例2】递归方程如下:

    (1)计算对应齐次方程的基础解析:

    特征方程为:C(t)=t^2-4t-4=0,得到一个2重根t=2.因而其基础解为:{2n      n*2n}

    (2)由于f(n)=n*2n,对应上面表格的最后一种情况,得到特解形式为:T(n)=n2(p0+p1n)2n代入原递归方程可得:p0=1/2,p1=1/6

    (3)原方程解的形式为:T(n)=a0*2n+a1*n*2n+n2(1/2+n/6)2n,代入T(0),T(1)得:a0=a1=0

    (4)综上:T(n)=n2(1/2+n/6)2n

    因而时间复杂度为:O(n32n)


     

    References:

    [1]青青的专栏:http://blog.csdn.net/metasearch/article/details/4428865

    [2]心灵深处博客:http://blog.csdn.net/metasearch/article/details/4428865

    [3]wikipedia中文:母函数

    [4]母函数的性质和应用:http://www.doc88.com/p-39037791334.html

    [5]关于递归算法时间复杂度分析的讨论:http://wenku.baidu.com/view/719b053331126edb6f1a1091.html

    [6][置顶]递归方程组解的渐进阶的求法——差分方程法:http://blog.csdn.net/explore_knight/article/details/1788046

    PS:博主python27对博客文章享有版权,网络转载注明http://www.cnblogs.com/python27/

    展开全文
  • master公式是分析分治递归时间复杂度问题: 公式主体 公式的主体是: T(N) = a*T(N/b) + O(N^d) 1) log(b,a) > d ->复杂度为O(N^log(b,a)) 2) log(b,a) = d ->复杂度为O(N^d*logN) 3) log(b,a) <...

    ~Ooops:本片博客为观看严蔚敏第二版的数据结构书籍所做的总结性笔记,

    有错误请望指出?

    master公式是分析分治法递归的时间复杂度问题:

    公式主体

    公式的主体是:

    T(N) = a*T(N/b) + O(N^d)
    1) log(b,a) > d ->复杂度为O(N^log(b,a)2) log(b,a) = d ->复杂度为O(N^d*logN)
    3) log(b,a) < d ->复杂度为O(N^d)
    

    变量解释:
    a:迭代子算法个数
    b:子算法所负责多少数据
    d:除去子过程剩下的时间复杂度的指数

    例子

    假设求出最大值的递归算法如下:

     public static int getMax(int[] arr, int left, int right) {
    
            if (left == right) {
                return arr[left];
            }
    
            int mid = (left + right) / 2;
            int leftMax = getMax(arr, left, mid);
            int rightMax = getMax(arr, mid+1, right);
            return Math.max(leftMax, rightMax);
        }
    
    分析代码

    易知代码在一次递归过程中是将此次的问题分解为如下:

    				
    			[		leftMax		] 					[		rightMax 		] 
    					左边最大值								右边最大值
    								return Max(leftMax , rightMax )
    

    递归是将原来的一个问题,划分成不同复杂度的子问题 , 所以 ,复杂度就是 子问题复杂度的 n 倍, 加上他们之间和并的复杂度 。

    套用公式分析

    以上所指, 套用公式 ,知 a 代表 迭代子算法个数 , 知 求最大值 ,问题被分成左右两个部分, 分别求出最大值 。所以 ,所以a = 2。

    b表示子算法所负责多少数据,知,left只负责N/2,right也只负责N/2的数据,所以b = 2;

    除去迭代算法,时间复杂度就是O(1),也就是N的0次方,所以d = 0;
    所以 ,套用公式为:

    T(N) = 2*T(n/2) + O(n^0)

    按照master公式分析复杂度的方法知 , 符合上述master公式的第一个分支 ,也就是求出的时间复杂度为O(N^log(b,a)).
    所以 ,求出此次分治法递归的时间复杂度为:O(N^log(2,2))= O(N)

    展开全文
  • 递归算法的复杂度分析 ...归并排序用的就是分治法的思想,数组长度为n,每层计算的事件复杂度为O(n),树的深度为O(logn),因此总的时间复杂度为O(nlogn)。 主定理 主定理,归纳了递归函数的时间复杂
  • 时间复杂度的计算方法最直接的是count循环中语句执行的次数,如2个嵌套的for循环的时间复杂度就是当入参为n时,最大的循环执行为n2,但是其中执行的语句不只是一条,所以可能每次循环执行了c条,所以最终的循环执行...
  • 那么分治递归是吉诺密结合在一起的 该怎么求复杂度呢? 这里有一个公式!!!!!!!!1 T(n)表示当前有n 个元素的时间 假设每次都分成a个子问题,每次子问题的规模是原问题的 1/b 如果当一个子问题太小的话就是...
  • 在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?...
  • 时间复杂度: 用T(n)T(n)T(n)表示排大小为nnn的数组的时间:T(n)=2T(n/2)+nT(1)=1T(n)=2T(n/2)+n T(1)=1T(n)=2T(n/2)+nT(1)=1 关于如何解这个递归方程,这里介绍其中一种,我们假设n是2的幂: 首先,我们递推关系式的...
  • 递归问题的时间复杂度分析广泛存在于分治法和DP中,根据算法导论的记载,可以使用主定理的公式直接计算。另外,这篇文章介绍一下使用迭代手算的过程。 主定理 迭代计算 有一点需要说明:2^k*T(n/2^k)...
  • 如何计算这种分治或者递归处理的算法的复杂度呢?   简单举个例子,很通用 我们设置解决这个问题需要的时间复杂度为T(N) 处理其中一半的问题时间复杂度为T(N/2),然后加上两边问题合起来一起处理一些特殊情况...
  • 在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?...
  • 分治策略时间复杂度计算

    千次阅读 2019-01-28 10:41:59
    在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子...
  • 所以,如果你要问我分治递归的关系,我会这样回答:分治依托于递归分治是一种思想,而递归是一种手段,递归式可以刻画分治算法的时间复杂度。所以就引入本文的重点:如何解递归式? 解递归式的三种方法:主定理...
  • 数据结构::递归时间复杂度的计算

    千次阅读 2016-11-26 22:11:43
    在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?...
  • 分治依托于递归分治是一种思想,而递归是一种手段,递归式可以刻画分治算法的时间复杂度
  • 根据主定理求递归时间复杂度

    千次阅读 2015-09-29 23:00:55
    在算法分析中,主定理(英语:master theorem)提供了用渐近符号表示许多由分治法得到的递推关系式的方法。此方法经由经典算法教科书《算法导论》而为人熟知。不过,并非所有递推关系式都可应用主定理。该定理的推广...
  • 在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?...
  • 在这个过程中,频繁地碰到到递归思想和分治思想,惊讶于这两种的思想的伟大与奇妙的同时,经常要面对的一个问题就是,对于一个给定的递归算法或者用分治思想缩小问题规模的算法,如何求解这个算法的时间复杂度呢?...
  • 维基百科——在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以...
  • 关于分治求众数和分治求幂时间复杂度的分析 记录一下第一次写CSDN,最近刚看了算法与数据结构的相关视频,其中看到了分治求众数和分治求幂的视频后对它们的时间复杂度的不同产生了强烈的探知欲,在看了一些博客后,...
  • 任何一个分治或者递归的函数都可以算出它的时间复杂度 关键4种 二分查找:发生在一个数列本身有序的时候,要在有序的数列中找到你要的目标数,所以每次一分为2只查一边,最后时间复杂度是O(logN) 从 T(n) = T(n/2) + O(1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,308
精华内容 523
关键字:

递归分治时间复杂度