时间与空间复杂度

时间维度是指执行当前算法所消耗的时间 即「时间复杂度」空间维度是指执行当前算法需要占用多少内存空间 即「空间复杂度」复杂度越高执行时间越长效率越低常见的时间复杂度量级有常数阶O(1)int i;int j;int a[100];//无论多长都只是一个复杂度对数阶O(logN)int c; for(int i1;in;i*2) { c;//复杂度为log2n }线性阶O(n)int c; for(int i0;in;i) { c;//复杂度为n }线性对数阶O(n logN)int c; for(int i1;in;i) { for(int j1;jn;j*2) { c;//复杂度为n*log2n } }平方阶O(n²)int c for(int i0;in;i) { for(int j0;jn;j) { c;//复杂度为n*n } }int c for(int i0;im;i) { for(int j0;jn;j) { c;//复杂度为m*n } }立方阶O(n³)int c for(int i0;in;i) { for(int j0;jn;j) { for(int k0;kn;k) { c;//复杂度为On*n*n } } }K次方阶O(n^k)例如 平方阶和立方阶 可知道k方阶指数阶(2^n)空间复杂度 算法在运行时临时占用的「额外内存大小」常见复杂度从好到差O(1)常数空间最好只用几个变量不随数据量变大。例a b、交换两个数。int i;O(log n)对数空间递归二分、树的高度。O(n)线性空间开了和输入一样长的数组。例复制数组、用数组存中间结果。int a[n];O(n²)平方空间很差开二维数组n 一大就爆内存。int a[n][n];