算法基础-01.算法复杂度的计算-主定理

作者: logi | 来源:发表于2020-03-28 09:17 被阅读0次

主定理的定义

『在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出，在那里被描述为解决这种递推的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen，Leiserson，Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。』（参考自百度百科）

主定理的公式

image.png

对于复杂代码我们可以通过分析代码的逻辑得到地推公式，拿以下公式为例：
例1：
$\begin{equation} T(n)=16 T(n / 4)+n \end{equation}$
我们可以得到：
$a=16,b=4$
$n^{log_b^a}=n^2>n=f(n)$
满足公式1，所以复杂度为
$T(n)=O(log_b^a)=O(n^2)$

例2：
$T(n)=4 T(n / 2)+n^{2}$

$a=4,b=2,f(n)=n^2$
$n^{log_b^a}=n^2log^0_n=f(n)$
满足公式2，所以复杂度为
$T(n)=O(n^2log^0_n)=O(n^2)$
其中，k=0!
例3：
$T(n)=16 T(n / 4)+n !$
$a=16,b=2,f(n)=n^2$
$n^{log_b^a}=n^2<n!=f(n)$
满足公式3，所以复杂度为
$T(n)=O(f(n))=O(n!)$

总结规律

得到 $a$ 和 $b$ 的值后与 $f(n)$ 比较大的就是其复杂度，如果相等须按照公式2推到一般都是 $O(n^xlogn)$

常见算法的复杂度

image.png

对于时间复杂度的分析可以用两种方法：

简单：看for循环
分治：master定理
动态规划：递归树方法

接下来介绍下树分析的方法

斐波那契时间复杂度和空间复杂度

$0、1、1、2、3、5、8、13、21、34$
$F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）$

时间复杂度：

image.png

求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2)，又必须先计算F(n-3)和F(n-4)。。。。。。以此类推，直至必须先计算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的结果，从而得到F(n)要计算很多重复的值，在时间上造成了很大的浪费，算法的时间复杂度随着N的增大呈现指数增长，时间的复杂度为 $O(2^n)$

空间复杂度：
如果不使用数组缓存中间的计算结果即完全递归，复杂度为 $O(2^n)$
如果使用数组缓存中间的计算结果，需要存储每个f(n)的值所以需要一个长度为n的数组，所以复杂度为 $O(n)$
如果使用递推公式的循环，所以复杂度为 $O(1)$

reference

https://zhuanlan.zhihu.com/p/53286463

网友评论

自然语言处理

本文标题：算法基础-01.算法复杂度的计算-主定理

本文链接：https://www.haomeiwen.com/subject/snfjuhtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

算法基础-01.算法复杂度的计算-主定理

主定理的定义

主定理的公式

总结规律

常见算法的复杂度

斐波那契时间复杂度和空间复杂度

reference

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

自然语言处理