时间、空间复杂度介绍

总结向/小白向介绍时间空间复杂度

复杂度分析

时间复杂度

渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系

O(1)

常量级的时间复杂度,代码计算规模不随着n增长而增长,如下代码:

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

O(logn)、 O(nlogn)

对数阶时间复杂度比较难分析,可以通过下面的代码看:

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

容易看出,算上面的时间复杂度,主要是算出第 3 行执行了多少次。列出公式:

$2^x = n$

只要求出 x 值,就可以得到时间复杂度,由高中知识可知:

$x = log_2n$

所以,复杂度是O($log_2n$)。

下面我们稍微改下代码:

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

易得时间复杂度是 O($log_3n$)。

因为对数之间是可以互相转换的:

$log_3n = log_32 * log_2n$

$log_3n = C * log_2n$

我们知道在时间复杂度的计算中,常数 C 是可以省略掉的,因此:

O($log_3n$) = O($log_2n$)

所以对数的底可以直接忽略掉,为O($logn$)。

时间复杂度O($nlogn$)就是把时间复杂度为O($logn$)的代码执行 n 次

O(m + n), O(m * n)

这种类型的时间复杂度由两块代码的数据规模共同决定,他们不是常数,比如:

void cal(int m, int n)
{
  int sum1, sum2, i, j;
  i = j = 0;
  sum1 = sum 2 = 0;
  for(i = 0; i < m; i++)
  {
    sum1 += i;
  }
  for(j = 0; j < n; j++)
  {
    sum2 += j;
  }
  
  return sum1 + sum2;
}

这里的时间复杂度由 m 和 n 的规模共同决定,故上面代码时间复杂度是 O(m + n)。

稍微改下代码:

void cal(int m, int n)
{
  int sum, i, j;
  i = j = 0;
  sum = 0;
  for(i = 0; i < m; i++)
  {
      for(j = 0; j < n; j++)
    {
            sum += i * j;
    }
  }
  
  return sum;
}

故上面代码时间复杂度是 O($m \times n$)。

最好时间复杂度

最好时间复杂度就是指在最理想的情况下,执行某一段代码的时间复杂度。

最坏时间复杂度

最好时间复杂度就是指在最糟糕的情况下,执行某一段代码的时间复杂度。

例子

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

从上面的代码看,之前我们的时间复杂度就无法进行分析了,因为如果在一开始就找到的需要寻找的元素,直接 break 的话,那么时间复杂度是O(1);如果到数组的最后才找到的话, 那么时间复杂度是O(n)。

平均时间复杂度

但是这两种情况都是最极端的情况,我们需要分析更可能出现的情况的概率,所以这里引入一个新的概念:平均时间复杂度

还是上面的例子,我们分析,从概率论上说,这个数字找到和找不到的概率都是 $\frac{1}{2}$ ,然后出现在 0 和 n - 1 这 n 个位置上的概率是 $\frac{1}{n}$。所以把各种情况都考虑进去的话, 平均时间复杂度的计算过程变成了:

$1 \times \frac{1}{2n} + 2 \times \frac{1}{2n} + \cdots + n \times \frac{1}{2n} + \frac{n}{2}$

$ = \frac{1}{2n} \times (1 + 2 + \cdots + n) + \frac{n}{2}$

$= \frac{1}{2n} \times \frac{(1+n)\times n}{2} + \frac{n}{2}$

$= \frac{1+n}{4} + \frac{2n}{4}$

$= \frac{3n + 1}{4}$

知道可以忽略复杂度中的系数和常数

O (n) = $\frac{3n + 1}{4} = \frac{3}{4}n + \frac{1}{4} =$ O(n)

上面这个值就是概率论中的加权平均值,也叫做期望值,所以平均时间复杂度的全称叫做加权平均复杂度,或者期望时间复杂度

空间复杂度

渐进时间复杂度,表示算法的存储空间与数据规模之间的增长关系

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]
  }
}

这里的空间复杂度只跟第 3 行的 n 有关系,也就是O(n)。就是这么简单,常用的空间复杂度一般有
O(1)、O(n)和O($n^2$)。

总结

越高阶的复杂度,效率越是低下;
时间复杂度从O(1), O($logn$), O(n), O($nlogn$), O($n^2$)依次递增;
空间复杂度一般是O(1)、O(n)和O($n^2$)。

参考文献:
数据结构与算法之美 - 王争

添加新评论

评论列表