算法导论：关于时间复杂T(n)的表达式处理

绝地灬酷狼 2022-03-20 04:59 65阅读 0赞

MIT算法导论提供了三种方法，不废话了，直接介绍：

( 公式显示不了，所有就截图了，请包涵~ 呵呵)

![1363767463_1508.jpg][]

**1.      代换法：猜测-> 验证**

例如：T(n) = 4\*T(n/2) + n (  其中T(1) =O(1)  )

假设是时间复杂度是n^3

那么证明：那么设T(k) <= c\*k^3;

那么带入有：T(n) = 4\*(n/2)^3 + n

= 1/2\*n^3 + n ~ O( n^3 )

**2.      递归树法：**

例如：T(n) = T(n/4) + T(n/2) + n^2

那么这种方法有一个特殊的表示方法：

T(n) 用下面的一颗树的表示！( 奇怪的表示形式 )

![1363767606_9195.jpg][]

那么我们可以看到，将每一行相加有：n^2                        第一行

5/16\*n^2               第二行

25/256\*n^2 …      第三行( if展开 )

每一行都会有一个n^2，那么显然有复杂度为O(n^2 )

**3.      Master Method：针对于T(n) = aT(n/b) + f(n)**

主要有三种情况需要记住：

**第一种：**当f(n) = O( n^(logba -e) );     ( e > 0的一个数)

注意：logba代表以b为底的a的对数( 不好表示 )

即当f(n)与n^(logba)是低阶的时候，

![1363767746_7312.jpg][]

![1363767815_3475.jpg][]

例如：1.T(n) = 4\*T(n/2) + n 则是第一种情况logba = 2,而n = n^1，所以1 < 2，所以为O( n^2 )

2. T(n) = 4\*T(n/2) + n^2 则是第二种情况，注意此处的k=0的，又logba = 2,所以2 = 2，所以为O( n^2 \* lgn )

3. T(n) = 4\*T(n/2)+ n^3，则是第三情况，3 >2，所有结果是：O( f(n)) = O( n^3 )

[1363767463_1508.jpg]: https://img-my.csdn.net/uploads/201303/20/1363767463_1508.jpg
[1363767606_9195.jpg]: https://img-my.csdn.net/uploads/201303/20/1363767606_9195.jpg
[1363767746_7312.jpg]: https://img-my.csdn.net/uploads/201303/20/1363767746_7312.jpg
[1363767815_3475.jpg]: https://img-my.csdn.net/uploads/201303/20/1363767815_3475.jpg

发表评论取消回复

表情：

评论列表（有 0 条评论，65人围观）

还没有评论，来说两句吧...

相关阅读

相关算法的时间复杂度

算法的时间复杂度是指在计算机执行该算法时所需要的时间和输入规模之间的关系。常见的时间复杂度有： 1. O(1)：常数时间复杂度，表示无论输入规模大小是多少，算法都需要相同的

分手后的思念是犯贱/ 2024年03月17日 09:10/ 0 赞/ 14 阅读

相关 [时间复杂度]-排序算法的时间复杂度

我们经常可以看到这样的描述：软件=数据结构+算法，可见算法基础对于一个程序员的重要性。算法中，有两个基本概念：时间复杂度和空间复杂度。时间复杂度：描述算法执行消耗的时

今天药忘吃喽~/ 2023年09月24日 14:38/ 0 赞/ 107 阅读

相关关于时间复杂度&什么是时间复杂度

文章目录简介常见的Big-Oh 简介精确的考虑程序运行时间会使得寸步难行，而且毫无意义，所以可以用一种“概量”的概念来衡量运行时间，称之为“时间

末蓝、/ 2023年09月23日 21:46/ 0 赞/ 60 阅读

相关算法的时间复杂度

算法一词，其实最早来源于数学领域。在数学领域中，我们最熟知的算法莫过于“高斯算法”了，即等差数列求和公式。那么在计算机领域中，也有众多的算法，排序、查找等都算。算法其实是有

女爷i/ 2022年09月16日 06:24/ 0 赞/ 186 阅读

相关关于时间复杂度的详解

\-宝宝为啥听不懂他们在讨论的时间复杂度 0.0 \-我怎么知道这个算法运行得比那个算法快 0.0 \-我究竟会不会超时0.0 \-我为什么还会超时0.0 \-时间复杂

分手后的思念是犯贱/ 2022年05月27日 13:11/ 0 赞/ 274 阅读

相关算法的时间复杂度

1.时间复杂度首先我们要知道什么是大O，教科书中有非常严谨的定义，但对于面试的我们并不需要去专文字游戏,我们需要理解它: n表示数据规模； O( f(n

心已赠人/ 2022年05月16日 01:36/ 0 赞/ 217 阅读

相关算法导论：关于时间复杂T(n)的表达式处理

MIT算法导论提供了三种方法，不废话了，直接介绍： ( 公式显示不了，所有就截图了，请包涵~ 呵呵) ![1363767463_1508.jpg][] 1

绝地灬酷狼/ 2022年03月20日 04:59/ 0 赞/ 66 阅读

相关算法的时间复杂度

文章目录 1. 各典型时间复杂度关系 2. 举例 2.1 对数级复杂度：O( log ⁡ 2 n \\log\_2n log2n)

深碍√TFBOYSˉ_/ 2022年02月22日 16:24/ 0 赞/ 427 阅读

相关算法的时间复杂度

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法

矫情吗；*/ 2021年12月22日 06:17/ 0 赞/ 305 阅读

相关算法时间复杂度

时间复杂度就是通常我们简称的复杂度，Ｏ(f(n))表示。常见的算法时间复杂度由小到大依次为： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n\2)＜

蔚落/ 2021年06月24日 15:57/ 0 赞/ 490 阅读