1、什么是时间复杂度
一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度(Time complexity)。
2、为什么要学习时间复杂度
首先我们知道一道算法题可以用多种算法来实现，算法在编写成可执行程序之后，运行时则需要消耗时间资源和空间资源，那么判断一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢。
3、时间复杂度分析方法的特点
- 不依赖具体的执行环境
- 不用具体的测试数据
- 在算法实现之前，在脑海中就可以评估算法的性能
4、时间复杂度的类型
1）常数阶O(1)
int x = 5; int y = 10; int result = x + y; System.out.println(result);
第一行语句执行1次
第二行语句执行1次
第三行语句执行1次
第四行语句执行1次
f(n) = 4 T(n) = O(4) T(n) = O(1)
只要你的程序执行的时间和输入数据规模n没有关系的话，即使需要成千上万行的代码，那么你的程序时间复杂度仍然是O(1)
2）对数阶O(log2n)
int i = 1;
for(;i <= n;i += i){
System.out.println(i);
}
第一次：i = 1 即 i = 2(1-1) = 20
第二次：i = 2 即 i = 2(2-1) = 21
第三次：i = 4 即 i = 2(3-1) = 22
第四次：i = 8 即 i = 2(4-1) = 23
第五次：i = 16 即 i = 2(5-1) = 24
....................
第x次：i = 2(x-1)
因为 i <= n，所以2(x-1) <= n，得到：x = 1 + log2n
f(n) =(4 + 3log2n) T(n) =O(4 + 3log2n) O(n) = log2n
再一例
int i = 1;
for (; i <= n; i = i * 3){
System.out.println(i);
}
第一次：i = 1 即 i = 3(1-1) = 30
第二次：i = 3 即 i = 3(2-1) = 31
第三次：i = 9 即 i = 3(3-1) = 32
第四次：i = 27 即 i = 3(4-1) = 33
第五次：i = 81 即 i = 3(5-1) = 34
....................
第x次：i = 3(x-1)
因为 i <= n，所以3(x-1) <= n，得到：x = 1 + log3n
f(n) =(4 + 3log3n) T(n) =O(4 + 3log3n) O(n) = log3n
log3n = log32 * (log2n)
O(log3n) = O(Clog2n)，其中常量C = log32
O(log3n) = O(log2n)
3）线性阶O(n)
for (i = 1; i <= n; ++1)
{
j = i;
j++;
}
第一行语句执行1+2n次
第二行语句执行n次
第三行语句执行n次
f(n) = 1+ 4n T(n) = O(1 + 4n) O(n) = n
4）线性对数阶
线性对数阶其实很好理解，就是将时间复杂度为对数阶的语句执行n遍。
5）平方阶O(n2)
for (x = 1; i <=n;x++)
{
for(i = 1;i <=n;i++)
{
j = i;
j++;
}
}
第一行语句执行1+2n次
第二行语句执行2n次
第三行语句执行n*n次
第四行语句执行n*n次
f(n) = 1+4n+2n2 T(n) = O(1+4n+2n2) O(n) = n2
6）立方阶O(n3)
与平方阶类似。平方阶是双层循环嵌套，则立方阶就是三层循环嵌套。
5、时间复杂度法则
1）加法法则
private static long sum(int n){
int sum1 = 0;
for (int i = 1; i <= 1000; i++){
sum1 += i;
}
int sum2 = 0;
for (int i = 1;i <= n; i++){
sum2 += i;
}
int sum3 = 0;
for (int i = 1;i <= n; i++){
for (int j = 1; j <= n; j++)
sum3 += i;
}
}
第一段for循环语句时间复杂度为O(1)
第二段for循环语句时间复杂度为O(n)
第三段for循环语句时间复杂度为O(n2)
如果：T1(n) = O(f(n)) T2(n) = O(f(n)) 那么：T(n) = max(T1(n),T2(n)) = max(O(f(n)),O(g(n))) = O(max(f(n),g(n)))
所以此算法的时间复杂度为O(n2)
再一例
private static long sum_1(int n,int m){
int sum1 = 0;
for(int i = 1; i <= 1000;i++){
sum1 += 1;
}
int sum2 = 0;
for (int i = 1; i <= n; i++){
sum2 += i;
}
int sum3 = 0;
for (int i = 1; i <= m; i++){
sum3 += i;
}
return sum1 + sum2 + sum3;
}
第一段for 循环语句时间复杂度为O(1)
第二段for循环语句时间复杂度为O(n)
第三段for循环语句时间复杂度为O(m)
此算法的时间复杂度为O(n + m)
2）乘法法则
private static long sum_3(int n){
int sum = 0;
for (int i = 1; i <= n; i++){
sum += sumSquare(i);
}
return sum;
}
private static long sumSquare(int n){
int res = 0;
for (int i = 1; i <= n; i++){
res += (i * i);
}
return res;
}
第一段语句时间复杂度为O(n)
第二段语句时间复杂度为O(n)
如果： T1(n) = O(f(n)) T2(n) = O(g(n)) 那么：T(n) = T1(n)*T(n) = O(f(n)*O(g(n))) = O(f(n)*g(n))
此算法的时间复杂度为O(n*n)
6、常用时间复杂度的排序
从小到大：O(1) < O(log2n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(3n) < O(n!) < O(nn)
标签：语句,执行,int,复杂度,算法,时间,数据结构 From： https://www.cnblogs.com/Santariki/p/16789835.html