算法基础概念-时间复杂度

2019-08-21

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省存储空间。时间、空间复杂度分析，就是衡量代码执行效率的工具。

大O复杂度表示法

如何在不执行代码的情况下，得到一段代码的执行时间？

// 累加函数
// 从CPU的角度看，每行代码都执行类似的操作：读数据-运算-写数据。假设每行代码执行时间都一样，为unit_time。
int cal(int n) {
  int sum = 0; // 1 unit_time
  int i = 1; // 1 unit_time
  for (; i <= n; ++i) { // n unit_time
    sum = sum + i; // n unit_time
  }
  return sum;
}
// T(n) = (2n+2)*unit_time

int cal(int n) {
  int sum = 0; // 1t
  int i = 1; // 1t
  int j = 1; // 1t
  for (; i <= n; ++j) { // nt
    j = 1; // nt
    for (; j <= n; ++j) { // n*n t
      sum = sum + i * j; // n*n t
    }
  }
}
// T(n) = (2n*n + 2*n + 3) * unit_time

T(n) = O(f(n))

第一个例子中T(n) = O(2n+2)，第二个例子中T(n) = O(2n²+2n+3)。这就是大O时间复杂度表示法。实际上并不具体表示代码真正的执行时间，而是代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度。

时间复杂度分析

通常我们会忽略公式中的常量、系数，只需要记录一个最大的量级，所以在分析算法时，只关注循环执行次数最多的那一段就可以了。

第一个例子中，循环最多的是for循环，执行了n次，所以时间复杂度为O(n)

总复杂度等于量级最大的那段代码的复杂度

第二个例子中外层循环执行n次，而内层执行n²次，所以时间复杂度为O(n²)

几种常见的时间复杂度

O(1)

1 2	int i = 9; int j = 6;

O(logn)、O(nlogn)

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

O(m+n)、O(m*n)

由两个数据的规模决定的。

空间复杂度

空间复杂度的全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {
  int i = 0; // 常量阶 和数据规模n无关 忽略
  int[] a = new int[n]; // 占用n大小，空间复杂度O(n)
  for(i; i<n; ++i) {
    a[i] = i * i;
  }
  for (i=n-1; i>=0; --i) {
    print out a[i]
  }
}