002-数据结构与算法-复杂度分析

什么是复杂度分析

数据结构和算法的最终目的,是让代码执行速度更快,占用空间更省。

而复杂度分析就是用来衡量代码是否够快,是否够省的指标。

复杂度分析包括时间复杂度(快)和空间复杂度(省)两个方面。

时间复杂度

计算方式

时间复杂度是用来估算代码执行时间随数据规模增长的变化趋势,通常用大O复杂度表示法表示:T(n) = O(f(n))

上面的公式中,T(n)表示代码的执行时间,f(n)表示每行代码执行次数的总和,而O表示T(n)与f(n)之间存在正比关系。

以下面的代码为例。

1 int cal(int n) {
2   int sum = 0;
3   int i = 1;
4   for (; i <= n; ++i) {
5     sum = sum + i;
6   }
7   return sum;
8 }

第4-5行的代码会各执行n次,其它代码都只执行1次,因此这段代码中f(n)=2n+3。

由于大O复杂度表示法是表示代码执行时间与数据规模增长之间的趋势,因此f(n)并不需要特别精确,只保留能代表趋势的部分就可以。

因此,通常会省略f(n)中的低阶,常数,系数部分。

对应到上面的公式,省略系数2和常数3,最后得到的时间复杂度就是:T(n) = O(n)

最好/最坏/平均时间复杂度

上面的例子比较简单,在实际场景中,时间复杂度分析要更加复杂,例如下面的例子。

// n 表示数组 array 的长度
1 int find(int[] array, int n, int x) {
2  int i = 0;
3  int pos = -1;
4  for (; i < n; ++i) {
5    if (array[i] == x) {
6        pos = i;
7        break;
8     }  
11  }
12  return pos;
13 }

注意第5-7行代码,当i满足一定条件时,会跳出当前for循环,因此这一段代码在最好的情况下只会执行1次,而最坏的情况下会执行n次。

这也分别对应了最好时间复杂度T(n) = O(1)以及最坏时间复杂度T(n) = O(n)

但在实际描述这段代码的时间复杂度时,既不会用最好,也不不会用最坏,而是用平均。

也就是计算在所有情况下,平均的时间复杂度是多少,这里就需要具备一定的数学基础了。

这里不详细描述上面代码平均复杂度的数学计算过程,直接给出答案,就是:n(n+3)/2(n+1),去掉低阶,常数,系数之后,最后的平均复杂度是T(n) = O(n)

常见的时间复杂度

常见时间复杂如下图所示:

空间复杂度

计算方式

空间复杂度与时间复杂度的概念类似,指的是算法的存储空间与数据规模之间的增长关系。

空间复杂度同样可以用大O表示法表示,以下面的代码为例。

1 void print(int n) {
2  int i = 0;
3  int[] a = new int[n];
4  for (i; i <n; ++i) {
5    a[i] = i * i;
6  }

7  for (i = n-1; i >= 0; --i) {
8    print out a[i]
9  }
10}

第3行代码中申请了一个大小为n的数据,其它部分占用的空间都是常数1,因此这段代码的空间复杂度是T(n) = O(n)

常见的空间复杂度

空间复杂度的种类比时间复杂度少很多,只有O(1)、O(n)和O(n^2 )三种。

上篇002-数据结构与算法-线性表
下篇001-Java基础-IO