时间复杂度

时间复杂度

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，接下来直接代码测试进行判断哪个更好，不用去嗯比系数。