一、度量一个程序（算法）执行时间的两种方法：
（1）事后统计法：将程序运行的时间记录下来进行统计和分析就是事后统计法。但是这种方法不太科学，原因有如下两点：
- 如果该程序执行所需时间非常慢（半个小时才能执行完毕），那么我们每次测试可能都需要等待这么久。
- 运行时间依赖于计算机硬件、软件等环境因素，这种方法需要在相同的计算机环境下运行才可以判断。
（2）事前估算法：通过分析估算某个算法的时间复杂度来判断哪个算法更优。 但是在介绍时间复杂度之前我们首先需要了解什么是时间频度。
二、时间频度：
基本介绍：一个算法花费的时间与算法中语句的执行次数成正比。哪个算法中语句执行次数愈多，他花费的时间也就越多。一个算法中语句的执行次数成为时间频度。记为 T(n).
举个例子：规定返回一个从start一直加到end之和。
public static int sum(int start,int end){
int result = 0;
for (int i = start; i <= end ; i++) {
result += i;
}
return result;
}
T(n) = n+1; （要加1是因为最后一次循环仍要执行一次判断）
public static int sum2(int start,int end){
return (start+end)*end/2;
}
T(n) = 1; (等差数列求和公式)
对于时间频度我们需要注意一下几点：
2.1常数项可忽略：
例如：T(n) = 2*n+100 ,T(n) =2n+50
n = 1 时 ： 102 , 52
n = 2 时 ： 104 , 54
n = 3 时 ： 106 , 56
n=10000 时 ： 20100 , 20050
从上面例子可以看出 当n趋近于无穷时,常数可忽略。
2.2低次项可忽略：
例如：T(n) = 2*n^2+3n+10 ,T(n) =2n^2
n = 1 时 ： 15 , 2
n = 2 时 ： 24 , 8
n=100 时 ： 20310 , 20000
2.3系数可忽略：
例如：T(n) = 3*n^2+2n ,T(n) =5n^2+7n
n = 1 时 ： 5 , 12
n = 2 时 ： 16 , 34
n=100 时 ： 30200 , 50700
有兴趣的可以把曲线图画一下，可以更直观的看出区别。
三、时间复杂度
定义：一般情况下，算法中的基本操作语句的执行次数时问题规模n的某个函数，用T(n)表示。若存在某个函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数（类似高等数学中的同阶无穷小），记作T(n) = O(f(n))。称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
看了上面一堆你可能已经蒙圈了。没关系，只要你现在能懂时间频度就可以看懂这个例子：
我们现在根据一个时间频度来试着推算一下时间复杂度：如：T(n) = 2n^2+7n+2 假设存在f(n) = n^2 ，那么当n趋近于无穷大时 T(n)/f(n) = lim n->正无穷 T(n)/f(n) = 2 ，等于一个常数 。 (洛必达法则)，现在就可以说该算法的时间复杂度为 O(n^2)。所以我们现在只需要弄清楚f(n)怎么求不就大功告成了吗？好的，重点来了。
重点如何计算f(n)：
- 用常数1代替时间频度表达式中的所有加法常数
- 修改后的时间频度表达式中，只保留最高阶项
- 去除最高阶项的系数
注意：T(n)不同的算法，时间复杂可能相同：如： T(n) = n^3+2n+1 与 T(n) = 2n^3+7
三、常见的几种时间复杂度
常数阶O(1)
对数阶O(log2n) (以2为底n的对数)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n^2)
立方阶O(n^3)
k次方阶O(n^k)
指数阶O(2^n)
常见的算法时间复杂度从小到大依次为：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(n^k) < (2^n)。时间复杂度不断增大，算法执行效率越低。
3.1常数阶O(1)
无论代码执行多少行，只要没有循环结构那么它的时间复杂度为O(1);
public static void consystant(int n){
int i=1;
n = i++;
}
可以看出不管n是2或者是10000执行的时间频度仍然是那固定的两行代码。
3.2对数阶O(log2n)
public static void log(int n){
int i = 1;
while(i<n){
i=i*2;
}
}
当while循环体执行时，每次都将i*2，也就是说i会距离n越来越近。假设x为循环的执行次数，那么2^x = n。大白话意思就是当i乘了2的x次时，i就不小于n了，也就是循环结束了。循环次数x就等于 log2n。所以时间复杂度为 O(log2n)。
3.3线性阶O(n)
相较于对数阶，线性阶很好理解。时间频度与n存在一次方关系，就称为线性阶。
public static void linear(int n){
for (int i = 0; i <n ; i++) {
System.out.println(n);
}
}
3.4线性对数阶O(nlog2n)
理解了对数阶，线性对数阶也比较好理解，即将时间复杂度为对数阶O(log2n)的代码循环执行n次。也就是n*O(log2n)，O(nlog2n)。
public static void linearNlog(int n){
for (int i = 0; i <n ; i++) {
while(i<n){
i=i*2;
}
}
}
3.4平方阶O(n^2)
说白了就是嵌套循环。
public static void square(int n){
for (int i = 0; i <n ; i++) {
for (int j = 0; j < n; j++) {
System.out.println(n);
}
}
}
