如何计算时间复杂度

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

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

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

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

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

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

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

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

  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 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

基于sliverlight + wcf的web 文字版IM 示例

演示地址: http://task.24city.com/default.html 预览界面: ? 一、布局 采用Grid布局,5行2列 第一行:为登录/注册信...

3266
来自专栏田超学前端

【微信小程序】c# 实现获取openid、session_key 服务端

6440
来自专栏张善友的专栏

通过SmtpClient发送Exchange会议邮件

看到C#中调用Outlook API 发起会议 ,这个完全可以用SMTP方式实现的,下面我的项目中使用的代码: 对于.NET而言,从2.0开始,发邮件已经是一件...

1949
来自专栏张善友的专栏

弹出式模态窗体选择文本控件

2006年就要到来了,最近比较忙,很少更新blog,今天发一个模态窗体选择文本控件辞旧迎新.新年在发几个asp.net2.0 webPart控件同各位分享: ...

1987
来自专栏C# 编程

C# 读取XML文件示例

有关XML文件编写规范,请参考:http://www.w3school.com.cn/xml/index.asp XML内容如下(文件名为:Informatio...

2170
来自专栏逍遥剑客的游戏开发

实现一个同步的RenderApplication

1414
来自专栏王磊的博客

MySQL数据库工具类之——DataTable批量加入MySQL数据库(Net版)

MySQL数据库工具类之——DataTable批量加入数据库(Net版),MySqlDbHelper通用类希望能对大家有用,代码如下: using MySql....

3699
来自专栏菩提树下的杨过

Silverlight:利用异步加载Xap实现自定义loading效果

关键点: 1.利用WebClient的DownloadProgressChanged事件更新下载进度 2.下载完成后,分析Xap包的程序集Assembly信息 ...

18610
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

1023
来自专栏跟着阿笨一起玩NET

从sql server 中读取二进制图片

441

扫码关注云+社区