1.概述

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，以及更加节省存储空间。考量快和省指标是：时间复杂度和空间复杂度。

2.大O复杂度表示法

int cal(int n){
        int sum = 0;
        int i = 1;
        for(; i<=n; i++){
            sum = sum+1;
        }
        return sum;
    }

假设每行代码的执行时间是unit_time，则第2行的执行时间是1个unit_time，第3行的执行时间是1个unit_time，第四和第五行的执行时间都是n个unit_time。则总的执行时间是2n+2个unit_time。 大O表示为：T(n)=O(2n+2)。但是一般只需要记录一个最大量级就就好。所以为：T(n)=O(n);

 int cal2(int n){
         int sum = 0;
         int i = 0;
         int j;
         for(; i<n; i++){
             j = 0;
             for(; j<n; j++){
                 sum = sum+i*j;
             }
         }
         return sum;
     }

同理，假设每行代码的执行时间是unit_time，则第2、3、4行的执行时间是1个unit_time，第5、6的行执行时间是n个unit_time，第7、8行的执行时间都是n^2个unit_time。则总的执行时间是2n^2+2n+3个unit_time。 大O表示为：T(n)=O(2n^2+2n+3)。最大量级表示：T(n)=O(n^2);

3.时间复杂度分析

1.只需关注循环次数最多的那段代码

比如一个函数里面有三段代码，第一二段的代码都是1个unti_time，第三段代码的执行时间的n个unit_time，则这个函数的时间复杂度是0(n)。

2.代码执行的常量次，无论常量多大都为O(1)

for(int = 0;i<100;i++)还是for(int = 0;i<1000;i++)，时间复杂度都为O(1)，因为无论100还是100都是常量。

3.嵌套代码中时间复杂度为最里面的一层代码的时间复杂度

比如：嵌套的3个for循环，第一层的复杂度n，第二层的复杂度为nn，第三层的复杂度为nn*n。（乘积法）。
时间复杂度为：n^3

4.常见的复杂度分析

1.O(1)

O(1)：常数阶。一般不涉及循环

2.O(logn)和O(nlog(n))

O(logn)和O(nlog(n))：对数阶。这种一般是变量会一直发生变化。比如：2^x=n。

3.O(2^n)、O(n)、O(n!)

O(2^n)：指数阶；O(n)：线性阶；O(n!)：阶乘阶。

3.空间复杂度

空间复杂度表示：算法的存储空间与数据规模之间的增长关系。

int cal3(int n){
        int sum = 0;
        int i = 0;
        int[] moeny = new int[n];
        for(;i<moeny.length;i++){
            sum = sum+moeny[i];
        }
        return sum;
    }

这段代码中，第2、3行需要申请的的存储空间是1，第三行申请的存储空间是n。剩余的代码并不需要存储空间。所以空间复杂度是：O(n)。