图文简析时间复杂度和空间复杂度_时间复杂度 ppt

简析时间复杂度和空间复杂度

衡量不同算法之间的优劣 ，主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。

空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

时间复杂度

常用时间复杂度分为这些      除了O(1)其他的都会根据数值的增大而增大

常数阶O(1)

void test(int n){
   System.out.println("1");
}

不管n为多大，此代码都只执行一次

对数阶O(logN)

 时间复杂度O(logn)—对数阶，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标

void test(int n){
   for(int i=1; i<n; i*=2){
       System.out.println("1");
   }
}

 线性阶O(n)

void test(int n){
    for(int i=0; i<n; i++){
        System.out.println("1");
    }
}

 n越大执行的时间就会越久

线性对数阶O(nlogN)

void test(int n){
    for(m=1; m<n; m++){
    	for(int i=1; i<n; i*=2){
       		System.out.println("1");
   		}
	}
}

 将时间复杂度为O(logn)的代码循环N遍，那么它的时间复杂度O(nlogN)。

平方阶O(n²)

void test(int n){
    for(x=1; x<=n; x++){
   		for(i=1; i<=n; i++){
       		System.out.println("1");
    	}
	}
}

O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)

立方阶O(n³)、K次方阶O(n^k)

O(n³)相当于三层n循环

O(n^k)相当于k层循环

指数阶(2^n)

int test(int n) {    
    if (n <= 1) {        
        return 1;
    } else {        
        return test(n - 1) + test(n - 2);
    }
}

类似于裴波那契数列

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1) 。

递归调用是有空间代价的：递归的深度是多少空间复杂度就是多少！

如果代码里面有数组，那么数组的长度，基本就是空间复杂度，

比如一个一维数组的长度为传入参数的个数，那么空间复杂度就是O(n)

比如一个二维数组，数组的长度为n平方，那么空间复杂度就是 n平方---- O(k^n)