复杂度分析

2021-08-18

大O表示法

O表示法”表示程序的执行时间或占用空间随数据规模的增长趋势。
大O表示法就是将代码的所有步骤转换为关于数据规模n的公式项，
然后排除不会对问题的整体复杂度产生较大影响的低阶系数项和常数项。

T(n) = O(f(n))
n：数据规模，通俗点说就是函数中的那个变量n。
f(n)：代码总的执行次数和数据规模的关系。
T(n)：代码的执行时间(并不是代码实际的执行时间，这里表示代码执行时间和数据规模之间的关系)。

常量阶O(1)) < 对数阶O(logn) < 线性阶O(n) < 线性对数阶O(nlogn)=nO(logn) <
平方阶O(n²)…立方阶O(n³)…k方阶 < 指数阶O( 2^n ) < 阶乘阶O(n!)

空间复杂度

//我们先假设每条语句的执行时间为单位时间unit_time
public int sums(int n){                   
        int a = 0;                        //unit_time
        int b = 0;                        //unit_time
        for ( i = 0 ; i < n ; i + +){     //unit_time * n
            a + = i;                      //unit_time * n
	}
        for( j = 0 ; j < 2 * n ; j + +){  //unit_time * 2n
            b + = j;                      //unit_time * 2n
	}
        return a + b;

即：T(n)=unit_time+unit_time+unit_timen+unit_timen=（2n+2）unit_time
当n趋于无穷大时，f(n)中的常数项对于整个公式的值的影响可以忽略，同样，
系数相比于数据规模n也可以忽略不计。
T(n)=O(f(n));
f(n)=2n+2; //常数舍去，2舍去，反正无穷大没变化
反正最后是O(n)。
常用的空间复杂度就是O(1)。像O(n²)、O(n³)、O(logn)、O(nlogn)这样的空间复杂度平时都用不到。
int[] m = new int[n];
m数组内新建n个元素,那么占用空间O(n)。