时间复杂度与空间复杂度

时间复杂度分析法

核心思想

忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。

1
2
3
4
5
6
7
8

int cal(int n) {
 int sum = 0;
 int i = 1;
 for (; i <= n; ++i) {
   sum = sum + i;
 }
 return sum;
}

2、3行是常量，可以直接排除，我们只看其中的for循环就可以了。上面代码的时间复杂度是：O(n)。

嵌套循环的分析法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int cal(int n) {
 int ret = 0; 
 int i = 1;
 for (; i < n; ++i) {
  ret = ret + f(i);
 } 
} 
 
int f(int n) {
 int sum = 0;
 int i = 1;
 for (; i < n; ++i) {
 sum = sum + i;
 } 
 return sum;
}

上面的代码，在cal()方法里面循环调用了f(),如果把前者循环里面的部分当作常量，那么前者的时间复杂度是O(n)，而后者的时间复杂度是O(n)，那么总共就是O(n x n)，也就是O(n²)。

常见的时间复杂度（数量级递增）

多项式量级

非多项式量级

当数据规模n越来越大时，非多项式量级的执行时间会急剧增加。

对数阶

1
2
3
4

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

变量i的值从1开始，每次循环都会x2，实际上就形成了一个等比数列：

1

2⁰  2¹  2² ...  2ˣ = n

这种形式就是对数阶，因为以2为底，计作O(log₂n)。又由于底可以忽略，所以记为O(logn)。

多数量级

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int cal(int m, int n) {
 int sum_1 = 0;
 int i = 1;
 for (; i < m; ++i) {
  sum_1 = sum_1 + i;
 } 
 int sum_2 = 0;
 int j = 1;
 for (; j < n; ++j) {
  sum_2 = sum_2 + j;
 }
 return sum_1 + sum_2;
}

这段代码即有m又有n，表示两个不同的数据量级，我们无法评估谁的数量级更大，所以两个都要考虑在内，记作O(m + n)。

空间复杂度

核心思想

排除常量、系数和运算，只记录最大空间占用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void print(int n) {
 int i = 0;
 int[] a = new int[n];
 for (i; i <n; ++i) {
  a[i] = i * i;
 }
 for (i = n-1; i >= 0; --i) {
  print out a[i]
 }
}

第二行代码申请了一个空间用来储存变量i，但由于是常量阶，可以忽略。

第三行代码申请了n个空间。

后续代码没有再继续申请空间。

所以空间复杂度就是O(n)。

常见空间复杂度