算法时间复杂度的计算

算法时间复杂度的计算一、算法时间复杂度定义在进行算法分析时候,语句总的执行次数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)


相关推荐

发表回复

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

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