如何计算时间复杂度

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

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

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

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

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

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

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

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

  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)

原文发布于微信公众号 - php(phpdaily)

原文发表时间:2015-11-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端吧啦吧啦

数据结构(二)之算法基础

3667
来自专栏一“技”之长

从一些简单的例子看算法时间复杂度 原

    在编程中,一段代码的执行效率实际上很难估算和预测,其主要受到如下几个方面的影响:

311
来自专栏趣学算法

数据结构 第9讲 数组与广义表

LOC(a00)表示第一个元素的存储位置,即基地址,LOC(aij)表示aij的存储位置。 授人以鱼不如授人以渔,告诉你记住公式,就像送你一条鱼,不如交给你捕...

612
来自专栏程序生活

TensorFlow入门:MNIST数据的单层逻辑回归代码单层回归代码输出结果

1644
来自专栏机器学习和数学

[编程经验] Tensorflow中的共享变量机制小结

今天说一下tensorflow的变量共享机制,首先为什么会有变量共享机制? 这个还是要扯一下生成对抗网络GAN,我们知道GAN由两个网络组成,一个是生成器网络G...

6753
来自专栏python读书笔记

《算法图解》note 6 图以及广度优先搜索和深度优先搜索1.图2.广度优先搜索3.深度优先搜索

1643
来自专栏决胜机器学习

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(九)——图的定义、存储与两种方式遍历 (原创内容,转载请注明来源,谢谢) 一、定义和术语 1、不同于线性结构和树,图是任意两个...

4367
来自专栏数据结构与算法

P1144 最短路计数

题目描述 给出一个N个顶点M条边的无向无权图,顶点编号为1~N。问从顶点1开始,到其他每个点的最短路有几条。 输入输出格式 输入格式: 输入第一行包含2...

33014
来自专栏郭耀华‘s Blog

TensorFlow 常用函数汇总

1032
来自专栏人工智能LeadAI

Python数据分析模块 | pandas做数据分析(二):常用预处理操作

在数据分析和机器学习的一些任务里面,对于数据集的某些列或者行丢弃,以及数据集之间的合并操作是非常常见的. 1、合并操作 pandas.merge pandas....

3416

扫描关注云+社区