一、定义
(1)如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。我们常用大O表示法表示时间复杂性,称之为大O记法。
(2)一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。常见的时间复杂度高低顺序如下:
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)
二、时间复杂度计算步骤
⑴ 找出算法中的基本语句;
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。
三、时间复杂度计算规则
(1)对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
(2)对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
(3)对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
(4)对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
(5)对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 咏月风雅公测福利大全 有哪些奖励
- dnf装备成长攻略
- 鸣潮丹瑾适配武器选什么 丹瑾四星五星武器推荐
- dnf装备指令输入怎么输入
- 《对马岛之魂》超越《战神4》成为PC最火爆PS游戏!
- 《生化1 重制版》首批细节曝光!击杀敌人要更多子弹
- 国产游戏崛起!这款海外乱杀的国产游戏《七日世界》 要来了
- 阿杜.2003-哈啰【海蝶】【WAV+CUE】
- 群星1990-国语畅销金榜第7集[日本版][WAV+CUE]
- 陈凡骐.2024-陈凡骐首张同名创作专辑【FLAC分轨】
- 《黑神话:悟空》官网新图 老猴子手捧金箍
- 国外玩家谈《黑神话:悟空》定价:别是70美元
- 晨报|《全境封锁:腹地》实机视频泄露 《对马岛之魂》PC玩家数破纪录
- Supper.Moment.2020-Everything.Is.You【寰亚】【WAV+CUE】
- 张美玲.1999-福建不朽民谣【南方】【WAV+CUE】