时间复杂度的计算

如果我们想验证一段代码的效率,一个最直接的办法就是编出来之后运行一下,这个方法称为事后统计方法,但是这个方法存在着非常大的弊端,比如我们需要时间编写代码,而代码写完后如果不符合要求需要重新编写;测试的方法会受到硬件和内存占有率的影响等等。所以为了让代码的评估更加规范和科学,我们更多的使用事前分析估计方法,即计算一个代码的时间复杂度。 其实一段代码的时间复杂度计算很容易,它是一种对计算次数的统计,它有如下几条规则: 1.用常数1取代运算次数中所有的加法常数。 2.只保留最高阶的项。 3.将最高阶的项前面的系数换成1. 这个方法被称之为大O阶方法。 我们通过几个例子看一看上述规则到底如何让使用:

int  sunm =0,n=100;    //执行1次
sum= (1+n)*n/2;        //执行1次
printf("%d",sum);      //执行1次

上面一段代码一共执行3次,但是时间复杂度是O(3)吗,按照规则1,上述代码的时间复杂度应该是O(1)

int i;                  //执行1次
for (i = 0;i<n;i++)     //执行n+1次
{
  printf("%d",i);       //执行n次
}

上面一段代码一共执行2n+2次,按照大O阶方法: 2n+2——2n+1 2n+1——2n 2n——n 上述代码的时间复杂度应该是O(n)

int i,j;                //执行1次
for (i = 0;i<n;i++)     //执行n+1次
{
    for (j = 0;j<n;i++) //执行n+1次
    {
        printf("%d",i);   //执行n*n次
    }   
}

上面一段代码一共执行n*n+2n+3次,按照大O阶方法: n*n+2n+3——n*n+2n+1 n*n+2n+1——n*n 上述代码的时间复杂度应该是

int i,j;                //执行1次
for (i = 0;i<n;i++)     //执行n+1次
{
    for (j = 0;j<m;i++) //执行n+1次
    {
        printf("%d",i);   //执行n*m次
    }   
}

上面一段代码一共执行mn+2n+3次,按照大O阶方法: mn+2n+3——n*n+2n+1 mn+2n+1——mn 上述代码的时间复杂度应该是O(m*n)

int count = 1;     //执行1次
while(count<n)   //执行k+1次
{
    count = count*2;  //执行k次
}

上述代码的时间复杂度应该是

最后给出常见的执行次数函数与其对应的时间复杂度:

常见时间复杂度排序:

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2782
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5767
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

38610
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2936
来自专栏杨龙飞前端

scrollto 到指定位置

2944
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4395
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

7166
来自专栏魂祭心

原 canvas绘制clock

5104
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

8668
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3675

扫码关注云+社区