什么是时间复杂度

当一个程序执行时,它所耗费的时间即是它的时间复杂度。

什么是空间复杂度

当一个程序执行时,它所占用的内存空间即是它的空间复杂度。

以常见的事情举例:小陈某天写了一个程序,它跑起来运行了 100ms,占用内存 16MB。这里边代码执行的时间成本以及空间成本即是 时间复杂度空间复杂度

时间复杂度的计算

常数阶

下面的算法运行次数为 1 时间复杂度记为:O(1)

1
2
int sum = 0;
sum = 100; //执行一次

线性阶

线性阶,以下面循环为例。因为循环体执行了 10 次 sum 的赋值而它的时间复杂度为:O(1),因此这段代码的时间复杂度计为:O(10)

1
2
3
4
int sum = 0;
for (int i=0;i<10;i++){
sum = i ; //时间复杂度为1的算法
}

对数阶

这是一段 while 循环代码中可以看到 number 每次执行都会乘 2 ,当 number 不小于 10 时就会退出循环。
那么它的时间复杂度是多少呢 ?

1
2
3
4
int number = 1;
while(number < 10){
number = number * 2;
}

number 的赋值情况是 1,2,4,8,16
我们可以设循环次数为 X , 2^X = n 得出 x = log2n ,因此得出算法的时间复杂度为 O(logn)

空间复杂度的计算

常量空间

分配的存储空间中为常量的时,此空间复杂度记作为:O(1)

1
int sum = 1666;

线性空间

当分配的空间是一个线性集合(如数组),空间复杂度为:O(4)

1
int [] array = new int[4];

二维空间

里是一个 Java 的二维数组,当二维数组的长宽成正比时,空间复杂度为:O(4^2) 即 4 的二次幂

1
int [][] array = new int[4][4];

待补充与修改