时间与空间复杂度

时间维度：是指执行当前算法所消耗的时间， 即「时间复杂度」

空间维度：是指执行当前算法需要占用多少内存空间， 即「空间复杂度」

复杂度越高，执行时间越长，效率越低

常见的时间复杂度量级有：

常数阶O(1)

int i;int j;int a[100];//无论多长都只是一个复杂度

对数阶O(logN)

int c; for(int i=1;i<=n;i*=2) { c++;//复杂度为log2n }

线性阶O(n)

int c; for(int i=0;i<n;i++) { c++;//复杂度为n }

线性对数阶O(n logN)

int c; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j*=2) { c++;//复杂度为n*log2n } }

平方阶O(n²)

int c； for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { c++;//复杂度为n*n } }

int c； for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { c++;//复杂度为m*n } }

立方阶O(n³)

int c； for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=0;k<n;k++) { c++;//复杂度为O（n*n*n） } } }

K次方阶O(n^k)

例如 平方阶和立方阶 可知道k方阶

空间复杂度 = 算法在运行时，临时占用的「额外内存大小」

常见复杂度（从好到差）

O(1)：常数空间（最好）只用几个变量，不随数据量变大。例：a + b、交换两个数。

int i;

O(log n)：对数空间递归二分、树的高度。

O(n)：线性空间开了和输入一样长的数组。例：复制数组、用数组存中间结果。

int a[n];

O(n²)：平方空间（很差）开二维数组，n 一大就爆内存。

int a[n][n];