算法时间复杂度的计算

算法时间复杂度的计算一、算法时间复杂度定义在进行算法分析时候,语句总的执行次数T(n)是关于问题规模n的函数,进而分型T(n)随着n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间度量记作:T(n)=O(f(n)).它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度.其中f(n)是问题规模n的某个函数.简单来说T…

大家好,又见面了,我是你们的朋友全栈君。

一、算法时间复杂度定义

        在进行算法分析时候,语句总的执行次数T(n)是关于问题规模n的函数,进而分型T(n)随着n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间度量记作:T(n)=O(f(n)).它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度.其中f(n)是问题规模n的某个函数.

简单来说T(n)代表时间频度:一个算法中语句执行次数称为时间频度

时间复杂度就是:算法的时间复杂度描述的是T(n)的变化规律,计作:T(n) = O(f(n))。

这里用大写的O( )来体现算法时间复杂度的记法,我们称之为大O记法.

二、推导大O阶方法(游戏秘籍三部曲)

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是1,则去除与这个项乘积的常数。

三、常数阶

let sum = 0, n = 100  //执行一次
sum = (1 + n) * n / 2  //执行一次
return sum //执行一次

这个算法的运行次数是f(n)=3,与n的大小无关
根据推导大O阶的方法,常数项3改为1,即时间复杂度为O(1)
对于分支结构(不含循环结构),无论真或假,执行的次数都是恒定的
不会随着n的变大而发生变化,其时间复杂度也是O(1)

四、线性阶

for(let i=0;i<n;i++){
   
   /* 这里是时间复杂度为O(1)的程序步骤序列*/

}

关键就是要分析循环结构的运行情况
上面这是一个for循环,那么它的时间复杂度又是多少呢?首先循环体就是一个执行一次的循环体,总共执行了n次,那么执行次数就是f(n) =n,启动我们的游戏攻略三部曲知道,时间复杂度就是为O(n).

五、对数阶

let count=1;
while(count<n){
    count=count*2
}

对数阶不是很好理解
每次count都会乘以一个2,他会距离n更近一步
这里详细解释一下
count=1时 1<n count=2 2的一次方
count=2时 2<n count=4    2的二次方
count=4时 4<n count=8    2的三次方

到2的x次方大于n的时候 循环就结束了
由2的x次方等于n –> x = logn,时间复杂度为O(logn)
常见的二分查找就是以上思路,时间复杂度为O(logn).

六、平方阶

for(let i=0;i<n;i++){
    for(let j=i+1;j<n;j++){
        
     /* 这里是时间复杂度为O(1)的程序步骤序列*/

    }
}

由于当i = 0时,内循环执行n此,当n = 1时, 执行了 n – 1 次, …当 i = n-1 时, 执行了1次,所以总的执行次数为:
n + (n -1) +( n -2 ) +… +1 = n(n +1)/2 = n^2/2 + n/2

根据我们的游戏秘籍的三部曲(保留最高阶,去除最高阶不是1的常数项),我们可以分析出来,时间复杂度为 O( n^2 ).

七、常见算法时间复杂度

算法时间复杂度的计算

 

笔者最近看《大话数据结构》,总结了一点,最后一张图网上找的。需要《大话数据结构》pdf高清电子版的铁汁留言,我在评论区发你!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/146697.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • java cloneable_java.lang.Cloneable的理解「建议收藏」

    java cloneable_java.lang.Cloneable的理解「建议收藏」以前也用过这个接口,那时是直接所有的东西都自己写了,也没发现问题。最近无意间发现这个接口的实现并不是想象中的那样,所以稍微研究了下,给大家分享一下。步骤:1、建立两个简单的POJO:Teacher和Student2、Teacher类实现了Cloneable接口,重写clone方法3、在main方法中建立teacher,然后clone,比较teacher和clone出来的teacherTeacher…

    2022年10月14日
  • GTM(Global Traffic Manager)和GSLB(Global Server Load Balancing)服务介绍「建议收藏」

    GTM(Global Traffic Manager)和GSLB(Global Server Load Balancing)服务介绍「建议收藏」最近看到一篇关于GSLB的文章,写的非常不错,学习了一下,这里做一些记录。一、GTM介绍GTM(GlobalTrafficManager的简写)即全局流量管理,基于网宿智能DNS、分布式监控体系,实现实时故障切换及全球负载均衡,保障应用服务的持续高可用性。GTM基于资源的健康状况及流量负载做智能调度决策,为用户提供最佳访问IP。网宿GTM,提供更可靠、稳定和安全的流量调度服务,助您轻松…

  • JSON字符串转为java对象

    JSON字符串转为java对象在日常的java开发中,我们经常会需要接收到其它地方传过来的数据,格式也很多都是通过JSON格式来传递的。所以我们经常需要将JSON格式的数据转换为我们所需要的数据格式,比如javabean形式。对于只有一层的JSON格式的数据转换还是比较简单的。代码如下:Stringparam="{‘leader’:’headtearch’}";JSONObjectjsonObject…

  • Chrome断点调试

    Chrome断点调试1.断点调试是啥?难不难?断点调试其实并不是多么复杂的一件事,简单的理解无外呼就是打开浏览器,打开sources找到js文件,在行号上点一下罢了。操作起来似乎很简单,其实很多人纠结的是,是在哪里打断点?(我们先看一个断点截图,以chrome浏览器的断点为例)步骤记住没?用chrome浏览器打开页面→按f12打开开发者工具→打开Sources→打开你要调试的js代码文件→在行号上单击…

  • 联想 p系列服务器,全面解读联想ThinkStation P系列工作站

    联想 p系列服务器,全面解读联想ThinkStation P系列工作站ThinkStationP900&P700【中关村在线报道】10月29日,在以”灵感澎湃创变未来”为主题新品发布会上,全新一代联想ThinkStationP系列工作站家族亮相。新品延续了品质、创新、人本设计三大Think基因,从外部设计到内部平台,进行了全面的优化和升级,整体性能较上代产品提升50%以上,并采用联想独家的Flex模块技术和三通道散热技术,将灵活扩展性、稳定可靠性提升至…

  • socket示例代码演示程序(螺纹)

    socket示例代码演示程序(螺纹)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号