【你问我答】如何清晰的理解算法中的时间复杂度?

问题描述:

如何清晰的理解算法中的时间复杂度?

回答有奖:

选取一位认真回答问题的牛友,赠送200牛币!

你问我答问题汇总:点击进入

------------
#我也有问题想询问牛友,怎么办?

欢迎私信@筱茜 说明你的问题,将根据问题具体情况排期进入【你问我答】专场~
私信请注明参与【你问我答】专场哦~

你问我答 - 答问题,成大佬,拿牛币!
你问我答是牛客新栏目,每周1期几个问题,
牛友在问题贴下留下自己的知识,经验与见解,
帮助更多牛友了解更多技术相关知识!
#悬赏#
全部评论
时间复杂度是衡量算法优劣的标准之一。 比如实际应用中同一个需求,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)
点赞 回复
分享
发布于 2019-05-28 15:10

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务