恒恒恒咩

V1

2022/06/22阅读:42主题:雁栖湖

时间复杂度

时间复杂度

1.常数时间操作

一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,这个操作叫做常数操作。

例子:int a=arr[i]; a将i位置的数取出,是一个固定的时间,与arr的数据量没有关系,这就是一个常数操作。

反之,int b =list.get[i];是一个链表,b取值需要从链表的开头一个一个取,i在第几千位,就要查看多少位,跟数据量有关,不是一个常数操作。

加减乘除,位运算等都属于常数操作。

2.时间复杂度

时间复杂度是一个算法流程中,常数操作数量的一个指标。常用o表示,读作big o。

具体来说,一个算法流程中进行了多少次常数操作(用N表示),总结出常数操作的数量表达式(N的表达式),只留下最高阶项,并且不要最高阶项的系数,剩下的部分如果为f(N),那么时间复杂度为o(f(N))。

3.评价算法流程好坏

评价一个算法流程好坏,先看时间复杂度指标,最高阶项数。如果相同,再分析不同数据样本下实际运行时间,也就是“常数项时间”。(就是看N表达式的系数,假如你N1是10,N2是100,但是N2的100中有很多位运算,N1的10中是加减乘除,无法直接因为10<100就说N1算法更好,因为加减乘除与位运算的常数操作时间不同,不确定,需要到实际情况下去实验哪个更好。)

遇到指标相同时,直接用实验的方式,将代码分别运行进行判断即可。

例子:

` public static void text1(){

int N =10000;

int a=0;

for(int i=0;i<N;i++){

a=12+100;

​ a=32*12;`

}

}

`public static void text2(){``

int N =10000;

int a=0;

for(int i=0;i<N;i++){

a=12|100;

a=746^12;

}

}

text1和text2的时间复杂度的指标相同都为N,接下来直接代码测试进行判断哪个更好,不用去嗯比系数。

分类:

后端

标签:

数据结构与算法

作者介绍

恒恒恒咩
V1