时间复杂度的计算

如果我们想验证一段代码的效率,一个最直接的办法就是编出来之后运行一下,这个方法称为事后统计方法,但是这个方法存在着非常大的弊端,比如我们需要时间编写代码,而代码写完后如果不符合要求需要重新编写;测试的方法会受到硬件和内存占有率的影响等等。所以为了让代码的评估更加规范和科学,我们更多的使用事前分析估计方法,即计算一个代码的时间复杂度。 其实一段代码的时间复杂度计算很容易,它是一种对计算次数的统计,它有如下几条规则: 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 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

NumPy二元运算的broadcasting机制

NumPy中有一个非常方便的特性:broadcasting。当我们对两个不同长度的numpy数组作二元计算(如相加,相乘)的时候,broadcasting就在背...

3328

在Python机器学习中如何索引、切片和重塑NumPy数组

在Python中,数据几乎被普遍表示为NumPy数组。

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

P3372 【模板】线段树 1 区间查询与区间修改

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式: 第一行包含两个...

2886
来自专栏ACM算法日常

递归算法复杂度Ω分析-分享

1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

331
来自专栏HTML5学堂

原生JS | 随机抽取不重复的数组元素 —— 有没有更好的方法?

HTML5学堂-码匠:从数组中随机抽取不重复的元素,构成新数组,拥有多种方法,来看看你用的方法性能如何? 效果的功能需求 从一个数组当中,随机抽取数个元素,构成...

3265
来自专栏有趣的Python

py编程技巧-1.3-如何统计序列中元素的出现频度

实际案例 某随机序列中,找到出现次数最高的三个元素,他们的出现次数是多少? 对某英文文章的单词进行词频统计,找到出现次数最高的10个单词,出现次数是多少? 普...

2825
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(二)——矩阵

        矩阵是Madlib中数据的基本格式,通常是二维的。在Madlib中,数组的概念与向量类似,数组通常是一维的,是矩阵的一种特殊形式。 一、矩阵表示...

1816
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

2739
来自专栏于晓飞的专栏

Java Integer 类 解读

Integer 类是Java中最常用的类型,它是原生类型 int 的包装类。在开发中我们基本可以将两者等价。但是,最近在开发中遇到一个 == 与 equals ...

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

BZOJ2339: [HNOI2011]卡农(dp 容斥)

直接转移会非常麻烦,因为要同时限制集合不同 xor不为0,我们又不知道集合的具体元素。

191

扫码关注云+社区