在看一个算法是否优秀时，我们一般都要考虑一个算法的时间复杂度和空间复杂度。现在随着空间越来越大，时间复杂度成了一个算法的重要指标，那么如何估计一个算法的时间复杂度呢？
首先看一个时间复杂度不同的两个算法，解决同一个问题，会有多大的区别。
下面两个算法都是用来计算斐波那契数列的，两个算法会有多大的差异。
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
/**
* 使用递归方式计算斐波拉契数列
* @param index 计算的项数
*/
public static long fibonacciUseRecursion(int index){
if(index <= 1){
return index;
}
return fibonacciUseRecursion(index-1) + fibonacciUseRecursion(index-2);
}
/**
* 不使用递归方式计算斐波拉契数列
* @param index 计算的项数
*/
public static long fibonacciNoUseRecursion(int index){
if (index <= 1){
return index;
}
long first = 0;
long second = 1;
for (int i = 0; i < index - 1;i++){
second = first + second;
first = second - first;
}
return second;
}
对上面两种算法进行简单的运行时间统计，我们使用下面的代码进行简单的测试
public static void main(String[] args) {
// 获取当前时间
long begin = System.currentTimeMillis();
// 计算第50项斐波拉契数列的值
System.out.println(fibonacciUseRecursion(50));
// 计算时间差，算法执行所花的时间
System.out.println("time:" + (System.currentTimeMillis() - begin) / 1000 +"s");
begin = System.currentTimeMillis();
System.out.println(fibonacciNoUseRecursion(50));
System.out.println("time:" + (System.currentTimeMillis() - begin) / 1000 + "s");
}
测试结果如下:
可以看到，在计算第50项的时候，第一种递归方式花费了48秒的时间，而第二种不到一秒，虽然这种方式不太科学，但也看出来了两者巨大的差距，并且随着计算的值越大，时间的差异越明显。由此可见，时间复杂度是决定一个算法好坏的重要指标。
上面我们使用了一种计算执行前后时间差的方式，直观的来看一个算法的复杂度，比较不同算法对同一组输入的执行时间，这种方法也叫作"事后统计法"，但是这种方法也存在一些问题，主要问题有：
那么我们可以使用代码的每个指令的执行次数，可以简单估算代码的执行次数，一般情况下，执行次数少的肯定要比执行次数多的花的时间更少。看如下的示例：
public static void test1(int n) {
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) {
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
上面这个方法，我们计算它的执行次数。
public static void test2(int n) {
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
上面这个方法，我们计算它的执行次数。
public static void test3(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
上面这个方法，我们计算它的执行次数。
public static void test4(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
上面这个方法，我们计算它的执行次数。
public static void test5(int n) {
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
上面这个方法，我们计算它的执行次数。
public static void test6(int n) {
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
上面这个方法，我们计算它的执行次数。
public static void test7(int n) {
for (int i = 1; i < n; i = i * 2) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
上面这个方法，我们计算它的执行次数。
public static void test8(int n) {
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
上面这个方法，我们计算它的执行次数。
使用这种方法我们发现计算会特别麻烦，而且不同的时间复杂度表达书也比较复杂，我们也不好比较两个时间复杂度的具体优劣，因此为了更简单、更好的比较不同算法的时间复杂度优劣，提出了一种新的时间
复杂度表示法---大O表示法。
大O表示法：算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
大O表示法，用来描述复杂度，它表示的是数据规模n对应的复杂度，大O表示法有以下的一些特性：
| 执行次数 | 复杂度 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 4n2+zn+2 | O(n2) | 平方阶 |
| 4log2n+21 | O(logn) | 对数阶 |
| 3n+2log3n+15 | O(nlogn) | nlogn阶 |
| 4n3+3n2+22n+11 | O(n3) | 立方阶 |
| 2n | O(2n) | 指数阶 |
复杂度的大小关系
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)。
因此上面的十个方法的复杂度如下：
|方法名称|复杂度|大O表式|
|-|-|-|
|test1|15|O(1)|
|test2|3n+1|O(n)|
|test3|3n2+3n+1|O(n2)|
|test4|48n+1|O(n)|
|test5|3log2(n)|O(logn)|
|test6|3log5(n)|O(logn)|
|test7|3nlog2(n) + 3log2(n) + 1|O(nlogn)|
|test8|3n+5|O(n)|
直接看表达式，还是很难判断一些复杂度的大小关系，我们可以借助可视化的一些工具来查看比如https://zh.numberempire.com/graphingcalculator.php，通过该网站我们看到在n变化的情况下，不同表达式的变换情况。
第一层计算5，只需要计算1次；第二层计算3和4，2次；计算第3层，4次；计算第4层，8次。所以总共计算1+2+4+8 =15= 25-1 = 1/2 * 22 -1
第一层计算6，只需要计算1次；第二层计算5和4，2次；计算第3层，4次；计算第4层，8次；第5层，计算10次。所以总共计算1+2+4+8+10 =25 = 25 - 7 = 1/2 * 26 - 7。
所以计算第n项，它的时间复杂度为O(2^n)。
所以最开始的两个算法，第一个的算法复杂度为O(2n),一个为O(n)。
他们的差别有多大？
原文：https://www.cnblogs.com/Leo_wl/p/12374695.html