精华内容
下载资源
问答
  • master定理

    千次阅读 2018-01-05 18:04:56
    平时设计或者阅读一个算法的时候,必然会提到算法的复杂度(包括时间复杂度和空间复杂度)。比如我们说一个二分查找算法...Master定理。 先插一句,在算法复杂度分析中,log通常表示以2为底的对数。 算法复杂度(算法

    平时设计或者阅读一个算法的时候,必然会提到算法的复杂度(包括时间复杂度和空间复杂度)。比如我们说一个二分查找算法的平均时间复杂度为O(logn),快速排序可能是O(n logn)。那这里的O是什么意思?这样的表达是否准确呢?

    今天来复习一下与算法复杂度相关的知识:函数渐进阶,记号O、Ω、θ和o;Master定理。

    先插一句,在算法复杂度分析中,log通常表示以2为底的对数。

    算法复杂度(算法复杂性)是用来衡量算法运行所需要的计算机资源(时间、空间)的量。通常我们利用渐进性态来描述算法的复杂度。

    用n表示问题的规模,T(n)表示某个给定算法的复杂度。所谓渐进性态就是令n→∞时,T(n)中增长最快的那部分。严格的定义是:如果存在 T˜(n)

    ,当n→∞时,有

    T(n)T˜(n)T(n)0

    就说 T˜(n)

    是T(n)当n→∞时的渐进性态。

    比如T(n) = 2 * n ^ 2 + n log n + 3,那么显然它的渐进性态是 2 * n ^2,因为当n→∞时,后两项的增长速度要慢的多,可以忽略掉。引入渐进性态是为了简化算法复杂度的表达式,只考虑其中的主要因素。当比较两个算法复杂度的时候,如果他们的渐进复杂度的阶不相同,那只需要比较彼此的阶(忽略常数系数)就可以了。

    总之,分析算法复杂度的时候,并不用严格演算出一个具体的公式,而是只需要分析当问题规模充分大的时候,复杂度在渐进意义下的阶。记号O、Ω、θ和o可以帮助我们了解函数渐进阶的大小。

    假设有两个函数f(n)和g(n),都是定义在正整数集上的正函数。上述四个记号的含义分别是:

    • f(n) = O(g(n)): c>0,n0N,nn0,f(n)cg(n)
    • ;f的阶不高于g的阶。
    • f(n) = Ω(g(n)): c>0,n0N,nn0,f(n)cg(n)
    • ;f的阶不低于g的阶。
    • f(n) = θ(g(n)): f(n)=O(g(n))&&f(n)=Ω(g(n))
    • ;f的阶等于g的阶。
    • f(n) = o(g(n)): ε>0,n0N,nn0,f(n)/g(n)<ε
      • ;f的阶低于g的阶。

      可见,记号O给出了函数f(n)在渐进意义下的上界(但不一定是最小的),相反,记号Ω给出的是下界(不一定是最大的)。如果上界与下界相同,表示f(n)和g(n)在渐进意义下是同阶的(θ),亦即复杂度一样。

      列举一些常见的函数之间的渐进阶的关系:

      • logn!=Θ(nlogn)

    • logn2=Θ(logn)

    • logn2=O(n)

    • n=Ω(log2n)

    • log2n=Ω(logn)

    • 2n=Ω(n2)

    • 2n=O(3n)

    • n!=o(nn)

    • 2n=o(n!)

      有些人可能会把这几个记号跟算法的最坏、最好、平均情况复杂度混淆,它们有区别,也有一定的联系。

      即使问题的规模相同,随着输入数据本身属性的不同,算法的处理时间也可能会不同。于是就有了最坏情况、最好情况和平均情况下算法复杂度的区别。它们从不同的角度反映了算法的效率,各有用处,也各有局限。

      有时候也可以利用最坏情况、最好情况下算法复杂度来粗略地估计算法的性能。比如某个算法在最坏情况下时间复杂度为θ(n^ 2),最好情况下为θ(n),那这个算法的复杂度一定是O(n ^2)、Ω(n)的。也就是说n ^ 2是该算法复杂度的上界,n是其下界。

      接下来看看Master定理。

      有些算法在处理一个较大规模的问题时,往往会把问题拆分成几个子问题,对其中的一个或多个问题递归地处理,并在分治之前或之后进行一些预处理、汇总处理。这时候我们可以得到关于这个算法复杂度的一个递推方程,求解此方程便能得到算法的复杂度。其中很常见的一种递推方程就是这样的:

      设常数a >= 1,b > 1,f(n)为函数,T(n)为非负整数,T(n) = a T(n / b) +f(n),则有:

      1. f(n)=O(nlogbaε),ε>0
      ,那么 T(n)=Θ(nlogba)
    • f(n)=Θ(nlogba) ,那么 T(n)=Θ(nlogbalogn)
    • f(n)=Ω(nlogba+ε),ε>0 ,并且对于某个常数c < 1和充分大的n有 af(n/b)cf(n) ,那么 T(n)=Θ(f(n))

      比如常见的二分查找算法,时间复杂度的递推方程为T(n) = T(n / 2) +θ(1),显然有 nlogba=n0=Θ(1)

      ,满足Master定理第二条,可以得到其时间复杂度为T(n)= θ(log n)。

      再看一个例子,T(n) = 9 T(n / 3) + n,可知 nlogba=n2

      ,令ε取1,显然满足Master定理第一条,可以得到T(n) = θ(n ^2)。

      来一个稍微复杂一点儿例子,T(n) = 3 T(n / 4) + n logn。 nlogba=O(n0.793)

      ,取ε = 0.2,显然当c = 3 /4时,对于充分大的n可以满足a * f(n / b) = 3 * (n / 4) * log(n / 4) <=(3 / 4) * n * log n = c * f(n),符合Master定理第三条,因此求得T(n)= θ(n log n)。

      运用Master定理的时候,有一点一定要特别注意,就是第一条和第三条中的ε必须大于零。如果无法找到大于零的ε,就不能使用这两条规则。

      举个例子,T(n) = 2 T(n / 2) + n log n。可知 nlogba=n1

      ,而f(n) = n logn,显然不满足Master定理第二条。但对于第一条和第三条,也无法找到大于零的ε使得 nlogn=O(n1ε) 或者 nlogn=Ω(n1+ε) ,因此不能用Master定理求解,只能寻求别的方式求解。比如可以利用递归树求出该算法的复杂度为 T(n)=O(nlog2n)

      。简单的说一下计算过程:

      递归树的建立过程,就像是模拟算法的递推过程。树根对应的是输入的规模为n的问题,在递归处理子问题之外,还需要nlogn的处理时间。然后根据递推公式给根节点添加子节点,每个子节点对应一个子问题。这里需要两个子节点,每个节点处理规模为n/ 2的问题,分别需要(n / 2) * log(n / 2)的时间。因此在第二层一共需要n *(log n -1)的时间。第三层节点就是将第二层的两个节点继续分裂开,得到四个各需要(n /4) * log(n / 4)时间的节点,总的时间消耗为n * (log n -2)。依此类推,第k(设树根为k = 0)层有2 ^ k的节点,总的时间为n * (log n- k)。而且可以知道,这棵树总共有logn层(最后一层每个节点只处理规模为1的子问题,无须再分治)。最后将每一层消耗的时间累加起来,得到:

      k=0lognn(lognk)=12nlogn(logn+1)=O(nlog2n)
    展开全文
  • Master定理

    2018-11-26 11:14:31
    转:http://www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html  
    展开全文
  • 记录 Master定理

    2020-02-02 22:51:56
    算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况,根据Master定理:o-渐进上界、w-渐进下界、O-渐进确界。 以下为3种常见情况: 设a≥1,b>1为常数,f(n)为函数,T(n)=aT(n/b)+f(n)为非负数,令x=...

    算法设计关于递归方程T(n)=aT(n/b)+f(n)复杂度之通用解法

    算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况,根据Master定理:o-渐进上界、w-渐进下界、O-渐进确界。

    以下为3种常见情况:

    设a≥1,b>1为常数,f(n)为函数,T(n)=aT(n/b)+f(n)为非负数,令x=logba:

    1.   f(n)=o(nx-e),e>0,那么T(n)=O(nx)。
      
    2.   f(n)=O(nx),那么T(n)=O(nx logn)。
      
    3.   f(n)=w(nx+e),e>0且对于某个常数c<1和所有充分大的n有af(n/b)≤cf(n),那么T(n)=O(f(n))。
      
    展开全文
  • 算法的复杂度与Master定理,介绍了算法的时间复杂度与空间复杂度的计算方法
  • 应用Master定理求解递归方程

    千次阅读 2015-10-04 15:33:02
    Master定理也叫主定理,它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。然而又应该如何应用Master快速求解递归方程式并且避开Master 定理的坑呢?本文中将会对这些问题...

    什么是Master定理

    简介

    Master定理也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。然而,Master定理也有其不适用的地方,下面会讲到。

    定义

    假设有如下递归方程:

    T(n)=aT(nb)+f(n)

    其中 n 为问题规模,a为递推的子问题数量且 a1 nb 为每个子问题的规模(假设每个子问题的规模基本一样)且 b>1 f(n) 为递推以外进行的计算工作。

    g(n)=nlogbn

    T(n)=Θ(g(n)),Θ(f(n)),Θ(g(n)lgn),g(n)f(n)>lgnf(n)g(n)>lgnf(n)=g(n)

    一句话概括就是谁大取谁,相等就乘 lgn

    不适用范围

    如上定义所述,当 g(n)f(n)<=lgn f(n)g(n)<=lgn 时,Master定理是无能为力的。因此,当遇到上面的情况时是不能使用Master定理的。

    怎么使用

    在应用Master定理时只需自己在心中默默的问上自己几个问题,就可以计算出递归方程的渐进复杂度。下面咱们走上一遍:

    1. a 是谁,b是谁, g(n) 是多少, f(n) 又是多少?
    2. g(n) 大还是 f(n) 大还是一样大?
    3. 如果 g(n) 大,那么 g(n)f(n)>lgn
    4. 如果 f(n) 大,那么 f(n)g(n)>lgn ?

    既然知道了怎么用,那下面就来几个例题再近距离感受下Master定理的强大。

    举几个栗子

    二分搜索

    二分搜索的递归方程如下:

    T(n)=T(n2)+Θ(1)

    按照上面的步骤,走上一遍试一下:

    在这里,
    1. a=1 , b=2 , f(n)=1 ,那么 g(n)=nlogba=nlog21=1
    2. f(n)=g(n)
    3. 因此 T(n)=Θ(g(n)lgn)=Θ(lgn)

    怎么样,是不是很简单。再举几个不同的栗子接着感受下

    二叉树遍历

    二叉树遍历的递归方程如下:

    T(n)=2T(n2)+Θ(1)

    继续按照上面的步骤走:

    1. a=2 , b=2 , f(n)=1 ,因此, g(n)=n
    2. g(n)
    3. g(n)f(n)=n>lgn
    4. 因此 T(n)=Θ(g(n))=Θ(n)

    依然不费力气,下面再来一个

    随便想的栗子一

    递归方程如下所示:

    T(n)=2T(n4)+Θ(nlgn)

    按照上面的步骤走:

    1. a=2 , b=4 , f(n)=nlgn ,则 g(n)=nlog42<n
    2. f(n)
    3. f(n)g(n)=nlgnnlog42>lgn
    4. 因此 T(n)=Θ(f(n))=Θ(nlgn)

    随便想的栗子二

    递归方程如下:

    T(n)=2T(n2)+Θ(nlgn)

    这次再按照上面的步骤走:

    1. a=2 , b=2 , f(n)=nlgn , 则 g(n)=n
    2. f(n) 更大
    3. f(n)g(n)=lgnlgn
    4. 因此,这个递归方程不能够使用Master定理解决

    通过上面的几个栗子应该能对Master定理感觉的差不多了吧?但其实,还是有点小小的问题的。

    一点问题

    我这篇博客里写的Master定理实际上并不是很严谨,为了更加简便理解与使用对原来的Master定理添加了些自己的理解在里面,完整的Master定理的定义可以参考下面维基百科的描述或者直接到《算法导论》中查看。

    当然,我理解的版本的Master定理或许有误,欢迎批评指正。

    展开全文
  • 递归方程的Master定理

    千次阅读 2017-02-23 22:06:27
    什么是Master定理 简介 Master定理也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。然而,Master定理也有其不适用的地方,下面会讲到。 定义 假设...
  • 简化版本的master定理

    2018-10-15 18:30:57
    今天看洛谷日报的时候,看到一个很有意思的东西,叫master定理,是关于计算时间复杂度的(主要针对初赛的选择题)。 这是今天洛谷日报的链接:https://www.luogu.org/blog/Chanis/master 时间复杂度 master...
  • master定理与时间复杂度

    千次阅读 2018-09-22 15:38:59
    在遇到递归方程求解时间复杂度,可以用master定理解决 
  • 学习master定理的起因是遇到的以下笔试题,虽然说看到有些网友说无法用master定理做… 以下将简要介绍master的理论知识、重点与例题。 整体导图逻辑为: master定理概念 使用方法及例题 预备小知识(Θ,O与Ω) ...
  • master\mathrm{master}master定理求解范围 对于一些递归性时间复杂度,由于难以计算,我们需要使用Master\mathrm{Master}Master定理来进行求解。 例如,我们熟悉的分治算法,其递归式为:T(n)=2T(n2)+nT(n)=2T(\frac...
  • 时间复杂度是衡量程序运行快慢的一个指标,为一个程序语句的执行次数。 在递归型程序中,时间复杂度并不好直接计算,这时我们需要运用Master定理
  • 文章目录算法基础算法的复杂度认识时间复杂度对数器Master定理相关链接公众号参考 算法的复杂度 算法复杂度(算法复杂性)是用来衡量算法运行所需要的计算机资源(时间、空间)的量。通常我们利用渐进性态来描述算法...
  • Master定理学习笔记

    2018-10-15 20:51:00
    \(Master\)定理,又称主定理,用于程序的时间复杂度计算,核心思想是分治,近几年\(Noip\)常考时间复杂度的题目,都需要主定理进行运算。 前置 我们常见的程序时间复杂度有: \(O(n)/O(n^2)/O(nlog_2n)/O(2^n)\)等等...
  • 二分法查找+Master定理

    2019-10-13 08:27:17
    Master定理用于快速得出递归算法时间复杂度。 from 百度百科 以下就是主定理的内容(from本站某篇文章截图,忘记了),以后遇到递归的T(n),可以直接按照下面的迅速得出递归的时间复杂度   网上有...
  • 分治法-Master定理

    2019-01-07 19:45:33
    一个大的复杂问题分为a个形式相同的子问题,这些子问题的规模为n/b,且分解或者合并的复杂度为f(n),那么总的时间复杂度可以表示为:  例如合并排序算法的时间复杂度递推求解如下:  ps:后面的O(n)表示一次...
  • 若取 m=n,则时间复杂度为 O(n^3) 14、递归算法的复杂性 15、合并算法讨论 Master定理的解释 是从一个高中生的博客‘借'来的,作为研究生不禁流下惭愧的泪水:(,不废话开始抄:) 正文 介绍master 定理前,首先要知道...
  • Master 理论中的递归函数: T(n) = aT(n/b) + f(n), (a>=1, b >1) 理解:aT(n/b)表示子项繁殖的速度, f(n)表示给定规模所需常规开销 记忆:记实例不记公式 实例1:merge排序 算法复杂度nlog(n) 递归函数:   ...
  • 定理 Master Theorem

    2020-11-29 22:00:25
    定理 Master Theorem 什么是主定理? 在算法分析中,主定理master theorem)提供了用渐近符号表示许多由分治法得到的递推关系式的方法。 主定理的作用? 简单来说是用来计算递归时时间复杂度的一种方法。 当有...
  • Master—Theorem 主定理的证明和使用

    万次阅读 多人点赞 2018-09-24 10:34:43
    Master——Theorem 正是用于快速得出递归算法时间复杂度的方法。 Master—Theorem 假设某个递归算法的时间复杂度递归公式为:T(n)=a∗T(nb)+ndT(n)=a*T(\frac{n}{b}) + n^{d}T(n)=a∗T(bn​)+nd,其中a&amp;amp;...
  • master theorem主定理

    2015-08-25 19:38:00
    为什么80%的码农都做不了架构师?>>> ...

空空如也

空空如也

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

master定理