文档章节

如何计算时间复杂度

李荣刚
 李荣刚
发布于 2015/02/04 15:01
字数 1106
阅读 102
收藏 4

求解算法的时间复杂度的具体步骤是:

  ⑴ 找出算法中的基本语句;

  算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

  ⑵ 计算基本语句的执行次数的数量级;

  只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

  ⑶ 用大Ο记号表示算法的时间性能。

  将基本语句执行次数的数量级放入大Ο记号中。

  如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:

  for (i=1; i<=n; i++)
  x++;

  for (i=1; i<=n; i++)
  for (j=1; j<=n; j++)
  x++;

  第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

  常见的算法时间复杂度由小到大依次为:

  Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。

这只能基本的计算时间复杂度,具体的运行还会与硬件有关。

 

上面的这部分内容是比较可靠的,理解的时候,可以参看着下面的这部分内容。

在计算算法时间复杂度时有以下几个简单的程序分析法则:

1.对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

2.对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

3.对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

4.对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))

5.对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:

(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))

(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

可以用以上法则对下面程序段进行简单分析

①for (i=0; i<n; i++)

② for (j=0; j<n; j++)

{

③ c[i][j] = 0;

④ for (k=0; k<n; k++)

⑤ c[i][j]= c[i][j]+ a[i][k]* b[k][j];/ * T5(n) = O(1) */

}

第①条与②③④⑤是循环嵌套T1(n)*T2(n)* (T3(n)+ T4(n)* T5(n))= O(n*n*n)即为整个算法的时间复杂度

O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)

本文转载自:http://blog.sina.com.cn/s/blog_50ce2abb0100vhem.html

李荣刚
粉丝 3
博文 18
码字总数 1040
作品 0
海淀
程序员
私信 提问
算法的时间复杂度计算

计算算法的时间复杂度,通常说的是算法的渐进增长时间复杂度,也就是随着数据的变大,该算法所需要的时间是如何增长的。 推导时间复杂度的原则 用常数1取代运行事件中的所有加法常数。 在修改...

光哥很霸气
2017/01/09
0
0
剑指offer__9:计算斐波那契数列的3种方法及复杂度分析

题目: 计算斐波那契数列第n项的值 n = 0, f(0) = 0; n = 1, f(1) = 1; n >= 2, f(n) = f(n-1) + f(n-2); 递归方法(not recommend) 针对递归方法的教学,斐波那数列可能是最常用来拿来举例...

RichardBillion
01/06
0
0
1.数据结构&算法的引言+时间复杂度

print(sumOfN(10)) print(foo(10)) start_time = time.time()for a in range(0,1001): end_time = time.time()print(endtime-starttime) 执行结果为: 0 500 500200 375 425375 200 425500 0......

杨洪涛
06/01
0
0
JavaScript 算法之最好、最坏时间复杂度分析

上一篇文章中介绍了复杂度的分析,相信小伙伴们对常见代码的时间或者空间复杂度肯定能分析出来了。 思考测试 话不多说,出个题目考考大家,分析下面代码的时间复杂度(ps: 虽然说并不会这么写...

snowLu
01/07
0
0
时间复杂度跟空间复杂度

时间复杂度:执行一个算法所需要的时间的衡量标准。 空间复杂度:执行一个算法所需要的空间的衡量标准。 拿时间换空间和拿空间换时间是优化算法的途径。 求时间复杂度: 如果算法的执行时间不...

李雷岗
2016/11/30
26
0

没有更多内容

加载失败,请刷新页面

加载更多

让《强化学习(第2版)》架起一座通往强化学习经典知识宝库的桥梁

上交大计算科学与工程系俞凯教授,5分钟口述讲解,带你快速认识了解年度重磅图书《强化学习(第二版)》! 在 AlphaGo战胜李世石之后,AlphaZero以其完全凭借自我学习超越人类在各种棋类游戏...

博文视点Bv
26分钟前
6
0
TLA7-EVM开发板的处理器、NOR FLASH、DDR3

TLA7-EVM开发板是一款由广州创龙基于Xilinx Artix-7系列FPGA自主研发的核心板+底板方式的开发板,可快速评估FPGA性能。核心板尺寸仅70mm*50mm,底板采用沉金无铅工艺的6层板设计,专业的PCB...

Tronlong创龙
35分钟前
4
0
UUID的变种-有序

为了解决UUID无序的问题,NHibernate在其主键生成方式中提供了Comb算法(combined guid/timestamp)。保留GUID的10个字节,用另6个字节表示GUID生成的时间(DateTime)。 /// <summary> //...

Canaan_
36分钟前
5
0
Netty学习(6)——通道间数据传输

1. FileChannel实现通道间的数据传输 在Java NIO中,如果两个通道中有一个是FileChannel,那你可以直接将数据从一个channel传输到另外一个channel。 transferFrom() FileChannel的transferF...

江左煤郎
39分钟前
4
0
AngularDOM操作

gtandsn
40分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部