时间复杂度和空间复杂度

时间复杂度

概念：

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

算法的渐进时间复杂度(公式)：T(n) = O(f(n))

算法的渐进时间复杂度概念：

若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

f(n)表示每行代码执行次数之和，O表示正比例关系

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

常数阶O(1): 它消耗的时候并不随着某个变量的增长而增长

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

线性阶O(n): 它消耗的时间是随着n的变化而变化的

for(i=1; i<=n; I++){
    j=i;
    j++;
}

对数阶O(logN): 在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了， 假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

int i = 1;
while(i < n){
    i = i * 2;
}

线性对数阶O(nlogN): 时间复杂度为O(logn)的代码循环N遍

for(m=1;m<n;m++){
    int i = 1;
    while(i < n){
        i = i * 2;
    }
}

平方阶O(n²): 把 O(n) 的代码再嵌套循环一遍

for(x=1; x<=n; x++){
    for(i=1; i<=n; I++){
        j=i;
        j++;
    }
}

O(n²)

for(x=1; x<=m; x++){
    for(i=1; i<=n; I++){
        j=i;
        j++;
    }
}

O(m*n)

立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)
都类似于平方阶

时间复杂度用时排序：

O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3)

空间复杂度（S(n)）

概念：

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

常见的空间复杂度量级有：O(1), O(n), O(n²)

空间复杂度 O(1)：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

空间复杂度 O(n)：第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间

• 一维数组a[n]：空间复杂度 O(n)
• 二维数组a[n][m]：空间复杂度 O(n*m)

int [] m = new int[n];
for(i=1; i<=n; I++){
    j=i;
    j++;
}