什么是时间复杂度?

菜园前端
• 阅读 302

原文链接:https://note.noxussj.top/?source=helloworld


什么是时间复杂度?

定性描述该算法的运行时间,一个函数、用大 O 表示,例如 O (1)、 O (n)、O (logN) ...

常见的时间复杂度量级

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

上面从上至下依次的时间复杂度越来越大,执行的效率越来越低。

坐标图如下

什么是时间复杂度?

基础案例

O(1)

当每次该文件执行的时候,以下代码永远只会执行一次。

let i = 0

i += 1

O(n)

这是一个循环语句,循环体内的代码会执行 n 次。

for (let i = 0; i < n; i++) {
    console.log(i)
}

O(1) + O(n) = O(n)

当两个时间复杂度的代码在一块时,以时间复杂度较大的为准,当 n 足够大的时候,1 可以忽略不计。

let i = 0

i += 1

for (let i = 0; i < n; i++) {
    console.log(i)
}

O(n) * O(n) = O(n ^ 2)

当遇到嵌套 for 循环时,两个时间复杂进行相乘,得到的结果就是真实的时间复杂度。当时间复杂度进行相加时,却可以忽略不计。

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        console.log(i, j)
    }
}

O(logN)

log 一般都是以 2 为底,可以不写。log 称为对数,一般是求 2 的多少次方为 n 。

let i = 1

while (i < n) {
    console.log(i)
    i *= 2
}
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
2年前
java 冒泡排序
思路1.将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;(第一轮结束后,序列最后一个元素一定是当前序列的最大值;)2.对序列当中剩下的n1个元素再次执行步骤1。3.对于长度为n的序列,一共需要执行n1轮比较时间复杂度最佳情况:T(n)O(n)最差情况:T(n)O(n2)平均情
Stella981 Stella981
2年前
Python数据结构与算法——散列(Hash)
!(https://oscimg.oschina.net/oscnet/19a7428dd9c64d149aa474d3aabe80ce.png)点击上方“蓝字”关注我们散列(Hash)对于一组数据项,顺序查找的时间复杂度是O(n),二分查找是O(logn),而对于散列的数据结构,
Stella981 Stella981
2年前
Redis 列表命令记录
新增的常用命令从列表右端插入值(1N个)(rpushlistkeycba)rpushkeyvalue1value2...valueN时间复杂度为O(1N)从列表左端插入值(1N个)(lpushlistkeycba)lpushkeyvalue1
Wesley13 Wesley13
2年前
BFPRT线性查找算法
介绍:BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂度,五位算法作者做了精妙的处理。时间复杂度O(N)算法步骤
Wesley13 Wesley13
2年前
C++ 顺序表 代码实现
线性表存储在计算机中可以采用多种方式,以下是按照顺序存储方式实现:优点:查找很方便缺点:插入元素、删除元素比较麻烦,时间复杂度O(n)1ifndefSeqList_h2defineSeqList_h3include<iostream4usingnamespacestd;
Stella981 Stella981
2年前
ImageMagick图像处理
合并图像dir命令行使用//示该目录下的所有文件名列表,并以A至Z字母顺序及数字顺序进行排列dir/o:ndir/o:n//按创建日期的顺序进行排列dir/o:ddir/o:d//按从小到大的顺序进行排列dir/o:sdir/o
菜园前端 菜园前端
1年前
什么是空间复杂度?
原文链接:什么是空间复杂度?算法在运行过程中临时占用存储空间大小的度量,和时间复杂度表示一样,一个函数,用大O表示,例如O(1)、O(n)、O(^2)...基础案例O(1)这段代码因为只声明了单个变量,单个变量所占用的内存永远是1。javascriptle
菜园前端 菜园前端
1年前
什么是顺序搜索?
原文链接:什么是顺序搜索?顺序搜索是一种比较低效的搜索算法,但是实现起来相对简单。主要步骤如下:1.遍历数组2.找到跟目标值相等的元素,就返回它的下标3.遍历结束后,如果没有搜索到目标值,则返回1基础案例时间复杂度:O(n)空间复杂度:O(1)javasc
京东云开发者 京东云开发者
6个月前
时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
归并排序归并排序遵循分治的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下:划分:分解待排序的n个元素的序列成各具n/2个元素的两个子序列,将长数组的排序问题转换为短数
京东云开发者 京东云开发者
6个月前
时间复杂度为 O (n^2) 的排序算法 | 京东物流技术团队
对于小规模数据,我们可以选用时间复杂度为O(n2)的排序算法。因为时间复杂度并不代表实际代码的执行时间,它省去了低阶、系数和常数,仅代表的增长趋势,所以在小规模数据情况下,O(n2)的排序算法可能会比O(nlogn)的排序算法执行效率高。不过随着数据规模增