复杂度

一、什么是时间复杂度

时间复杂度是指估算程序指令的执行次数（执行时间）。

对数公式是数学中的一种常见公式，如果a^x=N(a>0,且a≠1)，则x叫做以a为底N的对数,记做x=log(a)(N)，其中a要写于log右下。其中a叫做对数的底，N叫做真数 。 通常我们将以10为底的对数叫做常用对数，以e为底的对数称为自然对数。

二、什么是空间复杂度

估算所需占用的存储空间（占用的内存）。

三、大O表示法（Big O）

一般用大O表达式来描述复杂度（包含空间和时间），它表示的是数据规模n对应的复杂度，这只是大概的估算，能够帮助我们短时间内了解算法

1、忽略常数、系数、低阶：

1. 如果是常数，统一用O(1)表示，如时间复杂度为14，用O(1)表示

2. 如果是有系数的，统一用O(n)表示，去除常数和系数，因为2n的复杂度可能跟n一样，要系数没有意义

//比如0(2n) = 8 和 0(n) = 8 复杂度是一样的，要系数就没意义

3. 如果有更高阶的情况下舍弃低阶的和常数，系数也要舍弃。即3n^2 + 3n + 1 的复杂度为O(n^2)

空间复杂度：

public void test7(int n){
    int a = 1;
    int b = 2;
    int c = a + b;
    int[] array = new int[n];
    //时间复杂度O(n);
    //开辟的变量有n+1+1+1;空间复杂度为O(n)
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}

2、对数阶

1. （默认底数为一位，log后面跟的第一个数为底数）如果是log2(n) 、log3(n) 、logn(n) ，无论底数是什么常数，时统一称为logn，因为log2(n) = log2(9)* log9(n) （log2(9)为常数，忽略），所以忽略底数。最终复杂度为O(logn)

   public void test4(int n){
           //判断流程如下，假如n=8
           // 第一步 n=4
           // 第二步 n=2
           // 第三步 n=1
           // 第四步 n=0 (没有执行操作，所以只有3步，当n=8时，复杂度为3)
           //即 log2(8) = 3 所以以下执行次数为log2(n)
           while ((n = n / 2) > 0) {
               System.out.println("test");
           }
           //执行次数为log2(n)
           //大O表达式 O(logn)
       }

2. n为logn的阶级，所以 O(logn+nlogn)要丢弃低阶的数据，最终结果为O(nlogn)

 public void test6(int n){
        //n=n+n,与n = n*2一样
        //循环1执行次数 1+log2(n) +log2(n)
        for (int i = 0; i < n; n = n + n) {
            //循环2执行次数 log2(n)*(1+3n)
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
        //执行次数为1+2(log2(n)) + log2(n) + 3*nlog2(n) = 3*log2(n)+3*nlog2(n)+1
        //大O表达式 O(nlogn) 对于对数来说，n为logn的阶级，所以 O(logn+nlogn)要丢弃低阶的数据，最终结果为O(nlogn)
    }

| 执行次数 | 复杂度 | 非正式术语 |

| ---------------- | -------- | ---------- |

| 12 | O(1) | 常数阶 |

| 2n+3 | O(n) | 线性阶 |

| 4n^2+6n+6 | O(n^2) | 平方阶 |

| 4log2(n) +20 | O(logn) | 对数阶 |

| 3n+4nlog3(n)+17 | O(nlogn) | nlogn阶 |

| 4n^3+2n^2+22n+13 | O(n^3) | 立方阶 |

| 2^n | O(2^n) | 指数阶 |

复杂度O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)