关注
时间复杂度是衡量算法优劣的标准之一。 比如实际应用中同一个需求,A实现的代码运行要花100ms,而B实现的代码要花100s,从时间运算来说A的代码更优。 实际开发中,代码还没有运行,那么如何预知代码运行的时间呢? 受运行环境和输入规模影响,代码的运行时间无法预估,但可以预估代码基本操作的执行次数。 比如程序中以下常见的几种执行方式: T(n)=3n;执行次数是线性的。 T(n)=3logn;执行的次数是对数的。 T(n)=3;执行的次数是常量。 T(n)=3n2+3n;执行的次数是用多项式计算的。 有了基本算法操作执行次数T(n),根据n的取值确定哪一种运行的时间短。 为了解决时间分析,引入了渐进时间复杂度。 渐进时间复杂度:若存在函数f(n),使得当n趋近无穷大T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数,记作:T(n)=O(f(n)),O为算法渐进时间复杂度。 根据推出时间复杂度的基本原则:常数级用1表示;只保留函数中的最高阶项;省略最高阶的项数。 上面的执行方式用时间复杂度表示为: T(n)=O(n); T(n)=O(logn); T(n)=O(1); T(n)=O(n2); 当n足够大时其时间复杂度:O(1)<O(logn)<O(n)<O(n2)
查看原帖
点赞 评论
相关推荐
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
375360次浏览 7534人参与
# 在国企工作的人,躺平了吗? #
71101次浏览 859人参与
# 简历中的项目经历要怎么写 #
377138次浏览 6350人参与
# 应届生初入职场,求建议 #
21645次浏览 535人参与
# 晒一晒我的offer #
2789616次浏览 49654人参与
# 非技术岗薪资爆料 #
6458次浏览 131人参与
# 你更愿意参加线上面试还是线下面试? #
6207次浏览 90人参与
# 华为求职进展汇总 #
437346次浏览 4400人参与
# 租房前辈的忠告 #
20504次浏览 1621人参与
# 第一次面试 #
15230次浏览 236人参与
# 应届生应该先就业还是先择业 #
11845次浏览 113人参与
# 安利/避雷我的岗位 #
121877次浏览 2747人参与
# 机械人怎么评价今年的华为 #
53433次浏览 438人参与
# 谈薪时HR压价该怎么应对 #
32803次浏览 202人参与
# 通信硬件薪资爆料 #
143772次浏览 1059人参与
# 毕业租房也有小确幸 #
19666次浏览 1241人参与
# 除了offer,现在你还缺点啥? #
2479次浏览 50人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
22576次浏览 216人参与
# 来聊聊机械薪资天花板是哪家 #
20130次浏览 162人参与
# 如何确定求职岗位 #
101921次浏览 2416人参与