时间复杂度的计算

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

相关文章

来自专栏林冠宏的技术文章

Deque的部分成员函数 解析,关于这个类,百度有很多解析,唯独没有其函数介绍

函数 描述 c.assign(beg,end) c.assign(n,elem) 将[beg; end)区间中的数据赋值给c。 ...

1748
来自专栏http://www.cnblogs.com

redis缓存数据库

1154
来自专栏Redis源码学习系列

Redis源码学习之压缩列表

压缩列表是列表对象、哈希对象和有序集合对象的底层实现之一。以列表对象为例,当列表节点都是比较小的整数或者比较短的字符串的时候,Redis就会选择压缩列表来做底层...

400
来自专栏苦逼的码农

HashMap的存取原理你知道多少

在java的容器集合中,hashmap的使用频率可以说是相当高的。不过对于hashmap的存(put())以及取(get())的原理可能很多人还不大清楚,今天,...

1034
来自专栏白驹过隙

Redis - set类型操作

34913
来自专栏Python研发

Memcached·Redis缓存的基本操作

Memcached 是一个高性能的分布式内存对象缓存系统,用于动态Web应用以减轻数据库负载。它通过在内存中缓存数据和对象来减少读取数据库的次数,从而提高动态、...

1174
来自专栏desperate633

深入理解SortSet类型的使用及应用Redis 有序集合(sorted set)SortSet的应用场景SortSet的常用命令

Redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。

902
来自专栏mathor

LeetCode78.子集

 dfs经典题,对每一个数字都有一个boolean数组去对应,没选过就是false,选过就是true,在边界条件中进行枚举,将所有结果为true的下标对应的数值...

861
来自专栏海天一树

小朋友学C语言(12):判断

(一) 先动手编写一个程序: #include <stdio.h> int main() { if(1) { printf("T...

2699
来自专栏杨建荣的学习笔记

实用的位运算应用(r4笔记第97天)

对于位运算,之前在一篇博文中分享了一下在c语言和oracle中的位运算实现 http://blog.itpub.net/23718752/viewspace-1...

2695

扫码关注云+社区