网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

时间复杂度

2021/5/3 23:55:07 人评论

什么是时间复杂度 算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的&#…

什么是时间复杂度

    算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
     一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n),那么其对应的时间复杂度则记为O(f(n))。

常见的时间复杂度量级

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)
  • 指数阶O(2^n)

上面的量级从上至下依次的时间复杂度越来越大,执行的效率越来越低。
即:O(1) < O(logN) < O(n) < O(nlogN) <O(n²) < O(n³) < O(n^k) < O(2^n)
如下图所示
在这里插入图片描述

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?