什么是算法的大 O 表示法

做了这么多年的程序员，你是不是一直靠着自己的小聪明在编码，数据结构和算法可是前辈们的心血和经验总结，不可不研究。



数据结构是利用其存储结构和逻辑结构来有效地组织数据，比如线性的表、栈、队列，非线性的树、图等，而算法是描述运算的过程，它良好的算法是建立在有效的数据结构之上的。

评价算法的指标

评价一个算法的好坏，除了他正确性指标外，就是所消耗的时间和空间。

为了方便计算所消耗的时间，需要作2个假设：

1. 与计算机的软硬件无关，硬件好理解，软件比如编程语言、执行器、编译器等等；

2. 每个语句所消耗的时间都一样，记作一个单位时间；

举个例子

for (int i = 0; i < n; i++) { //①
  for (int j = 0; j < n; j++) { //②
    c[i][j] = 0; //③
    for (int k = 0; k < n; k++) { //④
      c[i][j] = a[i][k] + b[k][j] + c[i][j]; //⑤
    }
  }
}

如何计算它的消耗的时间呢

• 语句①循环到i=n时才会完结，所以它耗费n+1个时间单位；

• 语句②同语句①，自己的的循环中耗费n+1个时间单位，但它在①的循环n次中，所以消耗n*(n+1)个时间单位；

• 语句③在循环语句①②中，他们分别循环n次，所以语句③消耗n*n个时间单位；

• 语句④同③，但它本身执行n+1，所以语句④消耗n*n*(n+1)个时间单位；

• 语句⑤在循环语句①②④中，它消耗n*n*n个时间单位；

总体消耗的时间单位为：n+1 + n*(n+1) + n*n+n*n*(n+1)+n*n*n=2n3+3n2+2n+1；

算法的时间复杂度

上例中记得所得的时间是T(n)=2n3+3n2+2n+1，但用这么长的算式评价算法的好坏过于繁冗。实际上它是变量n的函数，可以表现出随着n的增大T(n)的增长率变化，可以进一步简化确定n的量级：T(n)=O(f(n)。T(n)=2n3+3n2+2n+1的最大量级是n3，因此可简化为T(n)=O(n3)，这就大O表示法。



大O表示法经常被用于计算机科学表示算法的复杂度或性能，它主要用于描述在最坏的情况下所花费的时间和空间(内存或磁盘)。



下面列举几个例子，根据上面的消耗时间单位的方法很容易计算

O(1)

O(1)表示算法总是执行相同的时间，比如

boolean isFirstElementEmpty(List<String> elements){
  return elements.get(0).isEmpty();
}

O(n)

O(n)表示算法是线性增长，其复杂度与数据集的大小成正比。

boolean ContainsValue(List<String> elements, String value) {
  for (String element : elements) {
    if (element.equals(value)) return true;
  }
  return false;
}

如果不用foreach，使用for会更直观些

boolean ContainsValue(List<String> elements, String value) {
  int n = elements.size();
  for (int i = 0; i < n; i++) {
    if (elements.get(i).equals(value)) return true;
  }
  return false;
}

它是消耗时间单位算式是1+n+1+n+1=2n+3，根据n的量级简化为大O表示即O(n)。

O(n2)

O(n2)表示算法的复杂度与数据集大小的平方成正比，一般的循环嵌套就是这种，随着嵌套的层级可能是O(n3)、O(n4)等。

boolean ContainsDuplicates(List<String> elements) {
  for (int i = 0; i < elements.size(); i++) {
    for (int j = 0; j < elements.size(); j++) {
      if (i == j) continue;
      if (elements.get(i).equals(elements.get(j))) return true;
    }
  }
  return false;
}

O(2n)

O(2n)表示算法的复杂度与数据集大小成指数增长，比如递归

int Fibonacci(int number) {
  if (number <= 1) return number;
  return Fibonacci(number - 2) + Fibonacci(number - 1);
}

O(log2n)指数复杂度

二分法查找时间复杂度最好的情况是O(1)，最坏的情况根据Master定理T(n)=T(n/2)+O(1)，所以是O(log2n)。它的原理是对于已经排序的数据集，先取中间值进行对比，成功即返回否则根据对别结果确定下一次的中间值对比，依次类推

int binarySearch(int[] arr, int value) {
  int start = 0, end = arr.length - 1;
  while (start <= end) {
    int middle = (start + end) / 2;
    if (value == arr[middle]) {
      return middle;
    }
    if (value > arr[middle]) {
      start = middle + 1;
    }
    if (value < arr[middle]) {
      end = middle - 1;
    }
  }
  return -1;
}

算法空间的复杂度

空间的复杂度的计算方法和时间复杂度一样，只是这里假设算法的指令、常数、变量和输入数据用到的寄存器相同，而只计算其用到的辅助空间单元个数。

实际上时间和空间是一对矛盾的冤家，一般情况下要么拿时间换空间，要么拿空间换时间，鱼和熊掌不可兼得。

复杂度对比

一般它的复杂度从小到达依次是O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)



最新、更多漫画请关注微信公众号：码农神说。

码农神说：图解码农技术，大话码农故事，漫画感悟码农人生，助力码农翻身！







• 百万并发「零拷贝」技术系列之经典案例Netty

• 缓存穿透、缓存击穿、缓存雪崩，看这篇就够了

• 一口气讲透一致性哈希(Hash)，助力「码农变身」

• 漫画 | 架构设计中的那些事

• Java 中异常处理的 9 个最佳实践

• Intellij IDEA 必备插件，提高效率的“七种武器”

• 接住喽，送你个装逼技能：JDK 动态代理

• 给“小白”漫画 + 图示讲解 MyBatis 原理，就问香不香!

• 辟谣：程序员不配谈恋爱？你错的可以！真相来了

• 面试官:CAP 都搞不清楚，别跟我说你懂微服务！

• 看看吧！28岁退休的程序员和P8都干了啥