这两个时间复杂度的计算方法怎么计算？求指教

来源：蜘蛛抓取(WebSpider) 时间：2016-08-04 12:19 标签： 算法时间复杂度计算
算法分析(2)-递归的时间复杂度
算法分析(2)-递归的时间复杂度
围观2717次
在前面的文章中，我们讨论了。很多算法是具有递归性质的，当我们的分析的时候得到的是递推关系的时间复杂度。
例如，在归并排序中，对一个给定的数组进行排序，我们把它分成两半，并对这两半递归地重复这个过程。最后，我们合并结果。时间复杂度可以写成：
T(n) = 2T(n/2) + cn. 还有许多其他算法，如二分查找，汉诺塔等都可以递推公式。
主要有三种方式来递归公式。
1）替代法：我们做一个猜测的解，然后用数学归纳法证明的猜测是正确的或不正确的。
例如：T(n) = 2T(n/2) + n。 我们猜测解为：T(n) = O(nLogn).
现在用数学归纳法来证明我们的猜测。
T(n) &= cn Logn.
我们可以假设对于值小于n时这个公式是成立的。
T(n) = 2T(n/2) + n
&= cn/2Log(n/2) + n
cnLogn - cnLog2 + n
cnLogn - cn + n
2）递归树方法
在这个方法中，我们得出一个递归调用树，并计算树的每一层的时间。最后，我们对各层相加。要绘制递归树，我们从给定的递归出发，一直递推下去直到我们找到里面的模式。这个模式一般是典型的等差或等比级数。
例如对这个递归方程：T(n) = T(n/4) + T(n/2) + cn^2
(cn2 即为 cn^2)
如果我们进一步分解表达T(n / 4)和T(n / 2), 　我们得到以下递归树。
(一直向下分解cn2)
要知道 T(n)的值，我们需要相加所有层的值。如果从最上面开始加，可以得到下面的式子：
= c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
上述系列是几何级数为5/16。
为得到一个上限,我们求无穷级数的和： (n^2)/(1 &#) 即为 O(n^2)
主定理是解决递归的一种直接方法。但仅用于一些类型或可以转换为以下类型的递归公式：
T(n) = aT(n/b) + f(n)
（a &= 1 且 b & 1）
有以下三种情况：
如何计算？
主定理主要来自递归树方法。如果我们画T(n) 的递归树 T(n) = aT(n/b) + f(n)，我们会发现 根节点的值为f(n) ，所有的叶子节点的和为
其中 c为 .
递归树的高度为：
在递归树的方法中，我们计算所有节点的和。如果在叶子节点的值是多项式的，那么叶子是占主导地位的一部分，而我们的结果变成叶子节点的值（情况1）。
如果叶和根是渐近一样的，那么结果就变成高度乘以在所有层的和（情况2）。如果根节点的值是渐近多，那么我们的结果变成在根的值（情况3）
一些时间复杂度可以使用主定理进行评估的例子
归并排序：为T(n) = 2T(n/2) + 。它属于在第二种情况， c为1并且
也1。因此该解决方案是
二分查找：T(n) = T(n/2) + . 。它也属于情况2.
c是0并且也为0。因此该解决方案是
1）主定理并不能用来解决所有形式为 T(n) = aT(n/b) + f(n) 的递归式，往往和给定的3种情况有第一定的差距。例如 T(n) = 2T(n/2) + n/Logn 不能用主定理解决。
2） 第二种情况可以扩展为 f(n) = .
如果 k &= 0 且 c = , 那么 T(n) =
参考：http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/
参考视频地址：
您可能还会对这些文章感兴趣！更多公众号：OfferGo专业的互联网求职经验分享、技术交流社区，帮助你找到二线以上互联网公司的IT工作。由硅谷和国内顶尖IT企业工程师联合创立与维护。提供专业的编程语言、数据结构，算法等培训与面试咨询。最新文章对这篇文章不满意？您可以继续搜索：百度：搜狗：感谢您阅读如何分析算法的时间复杂度和空间复杂度，本文可能来自网络，如果侵犯了您的相关权益，请联系管理员。QQ:当前位置：
> > 查看文章
时间复杂度和空间复杂度2 – 数据结构和算法04
时间复杂度和空间复杂度2
让编程改变世界
Change the world by program
算法时间复杂度
我们说好的时间复杂度和空间复杂度呢？
历来大学老师在讲解这两个概念，都是直接登堂入室，导致八成学生对概念理解不深刻，或者说只是硬背起来而已。
为了让大家能够更好地接受这两个比较重要的概念，我们有了上一讲的准备环节。
这一讲我们直接切入正题，介绍计算复杂度的攻略，然后通过一系列例子和大家一起分析总结规律。
算法时间复杂度的定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。
算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
好长好长，没想到定义这个概念的老家伙比小甲鱼还罗嗦。（关键需要知道执行次数==时间）
这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。
显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别为O(1)，O(n)，O(n^2)。
三个求和算法？哪有？忘了？
好吧，看看以下这张图能不能勾起点回忆？
算法时间复杂度
推导大O阶方法
那么如何分析一个算法的时间复杂度呢？即如何推导大O阶呢？
我们给大家整理了以下攻略：
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项存在且不是1，则去除与这个项相乘的常数。
得到的最后结果就是大O阶。
世界上的东西就是这么简单，老头儿们把它讲复杂，那么它就复杂了，举几个例子：
&&&int sum = 0, n = 100;
(“I love fishc.comn”);
(“I love Fishc.comn”);
(“I love fishC.comn”);
(“I love fIshc.comn”);
(“I love FishC.comn”);
(“I love fishc.comn”);
sum = (1+n)*n/2;
大家觉得这段代码的大O是多少？
分页阅读：
小甲鱼在干啥
如果您觉得小甲鱼的视频能够给您带来知识和快乐，您可以选择赞助我们，让我们可以持续为您推出更多精彩的原创编程教学^_^
手机用户打开支付宝钱包，扫描下方支付宝二维码即可：
电脑用户点击下方按钮即可跳转至支付宝转账页面：
感谢您对我们发展的支持和认可！
更多新鲜事儿
加载中……扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
浙ICP备号-2
扫一扫，把题目装进口袋共有 4885 人关注过本帖
标题：如何计算一个算法的时间复杂度
等　级：新手上路
帖　子：83
&&问题点数：0&&回复次数：10&&&
如何计算一个算法的时间复杂度
void fun(int n)
&&&&int i=0,j;
&&&&&&&&for (j=0;j&n;j++)
&&&&&&&&&&&&i+=j;&&&&
&&&&}while (i&n+1);
讲下详细的解题过程
搜索更多相关主题的帖子:
来　自：南师大
等　级：论坛游民
帖　子：59
专家分：15
[[it] 本帖最后由 jdh99 于
10:50 编辑 [/it]]
等　级：新手上路
帖　子：45
如何计算一个算法的时间复杂度
题目就不明白什么意思
void fun(int n)
&&& int i=0,j;
&&&&&&&&for (j=0;j&n;j++)
&&&&&&&&&&&&i+=j;&&&
&&& }while (i&n+1);
for(i=0;i&n+1;)
&&& for (j=0;j&n;i+=j,j++);
[[it] 本帖最后由 scheelite 于
11:04 编辑 [/it]]
等　级：新手上路
帖　子：374
外循环无用，复杂度T(n)
来　自：金星
等　级：ID已被封
帖　子：193
一般是计算&&最内层循环的 那个对程序总运行时间贡献最大的 操作 的 执行次数
CPU的处理能力一般是每秒执行百万条指令&&&两者对照一下就可以粗略估计程序的运行时间
你可以试试估计一下汉诺塔（64层）程序的运算时间 2^64-1
2^10≈10^3&&2^64≈16*10^18=16*10^12*10^6=310*16世纪
//执行10^6次条指令需1秒&&10^8秒≈3.1年&&10^10秒 ≈ 3.1世纪
[[it] 本帖最后由 网易 于
12:55 编辑 [/it]]
答案是：雨中飞燕！
等　级：论坛游民
帖　子：34
专家分：20
我承认我是菜鸟，算复杂度只想到求循环次数，而且是能看懂程序的前提下
附件: 只有本站会员才能下载或查看附件，请
只要功夫深铁杵磨成针
等　级：业余侠客
帖　子：474
专家分：236
书上讲得很清楚也很详细。大O的定义和在数学分析中的定义是一样的。
without further ado, let’s get started
等　级：论坛游民
帖　子：48
专家分：16
菜鸟我最大！
等　级：新手上路
帖　子：21
void fun(int n)
&&& int i=0,j;
&&&&&&&&for (j=0;j&n;j++)
&&&&&&&&&&&&i+=j;&&&
&&& }while (i&n+1);
大哥，这程序好像太那个了
退出for循环
i=6!&(n+1)=4
do循环只做了一次
这是啥意思
来　自：金星
等　级：ID已被封
帖　子：193
[bo][un]风居住的街道[/un] 在
11:26 的发言：[/bo]
外循环无用，复杂度T(n)
还没见过用T（n）表示复杂度的&&T（n）表示时间的吧
O（g(n)） ⊙(g(n))&&Ω(g(n))　　都见过了&&不过很少见人用
答案是：雨中飞燕！
版权所有，并保留所有权利。
Powered by , Processed in 0.030751 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved

我要回帖

更多关于 算法时间复杂度计算 的文章

 

随机推荐