算法复杂度

1.复杂度分析。
复杂度分析是为了获取到如何更快地处理和解决现实场景中我们所遇到的问题，因为我们需要对效率和资源消耗有一定的要求。

2.事后统计法。
这种统计方法具有一定的局限性，首先得把程序写出来，然后执行统计。是无法真是反应出算法的性能的。

3.大O表示法：T(n)=O(f(n))。
f(n)代表每行代码执行的次数总和，n代表数据规模的大小，执行规模的增大与代码执行时间的增长率成正比。T(n)代表执行时间总和。这个公式代表的意思是随着规模n的增大，算法执行时间的增长率和f(n)的增长率是相同的，随着数据规模的增长代码执行时间的变化趋势。

4.时间复杂度。
其相比于空间复杂度，时间更为重要，因为时间一去不复返，而空间可以通过物理手段去优化。

时间复杂度分析

1.我们只需要关注循环次数最多的那一段代码即可。

void test(){
        for(int m=0;m<5;n++){
        ...
        }

        for(int m=0;m<10;n++){
        ...
        }
    }

如上方法我们只需要关注m<10的时间复杂度即可。

void test(int m,int n){
        for(int i=0;i<m;m++){
        ...
        }

        for(int i=0;i<n;n++){
        ...
        }
    }

如上方法如果m，n是由调用者传入的，我们不确定的m和n的大小的时候，此刻的时间复杂度为O(m+n)。

2.一个方法的总复杂度等于最高阶项的复杂度。

void test(int n){
        for(int m=0;m<n;n++){
        ...
        }

        for(int m=0;m<n;n++){
            for(int i=0;i<n;i++){
            ...
            }
        }
    }

例如如上的时间复杂度看的是双层for的时间复杂度。

3.嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

void test(int n){
        for(int m=0;m<n;n++){
            for(int i=0;i<n;i++){
            ...
            }
        }
    }

如上方法的时间复杂度为O(n2)。

4. 常见的时间复杂度

O(1)：常数阶
O(n)：线性阶
O(n2)：平方阶
O(log(n))：对数阶
O(nlog(n))：线性对数阶
O(n3)：立方阶
O(2n)：指数阶
O(n!)：阶乘阶

他们从小到大的排序依次是：
O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

一般来讲，如果我们通过算法写出来的程序的时间复杂度为O(n2)的时候都需要综合考虑，如果大于等于了O(n3)，那我们的这个写法就没有任何意义了，哪怕n特别小。时间复杂度大于等于了O(n3)我们称之为NP，意为随着n的增加，时间复杂度急剧上升，求解问题的时间会无限增长，那也就没有存在的必要了。

空间复杂度分析

空间复杂度相比于时间复杂度要简单得多，其代表的是算法的存储空间与数据规模之间的增长关系。

void test(int n){
        int m = 0;
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = m+1;
        }
    }

如上方法，m是一个常量，与数据规模n无关，所以m忽略，然后创建了一个长度为n的数组。如果说方法执行所需要的辅助空间相对于数据规模来说是一个常数，我们将之称之为原地工作，其空间复杂度就为O(1)。

常见的空间复杂度还有O(n)，O(n2)…等等。