大 O 表示法

大 O 表示法是一种特殊的表示法，指出了算法的速度有多快。

在我们的日常工作中，基本都是使用其他人编写好的算法，基本不太在乎算法的速度到底有多快。
但是，人要往高处走嘛~最重要的是，面试的时候，面试官肯能会问...
那么我们今天来简单的了解一下 大 O 表示法 。

• 大O表示法 是什么样子？

大O表示法
指出了算法需要执行的操作数。之所以叫大O表示法就是因为操作数前有一个大O，就是这么随意...

• 举个栗子
  假设有一个数组，包含了n个元素。简单查找，也就是从数组的第0项（索引项）找到某个元素，需要从头检查到尾，因此需要执行 n 次操作。使用大O表示法，这个运行时间为 O(n)。单位呢？没有--大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
  再比如，为了检查长度为 n 的数组，二分查找法需要执行logn次操作。使用大O表示法就是 O(logn) 。

• 大O表示法指出了最糟糕情况下的运行时间
  假设有一个数组[1,2,3,4,5]，如果使用简单查找要查找“1”的话，一次就能找到，但是即使这样，算法的运行时间依旧是O(n)而不是O(1)。

• 常见的大O运行时间

  • O(log n) 也叫对数时间，这样是算法包括二分查找法
  • O(n) 也叫线性时间，这样的算法包括简单查找
  • O(n*log n) 这样是算法包括快速排序--一种比较快的排序算法
  • O(n²) 这样的算法包括选择排序--一种比较慢的排序算法
  • O(n!) 这样的算法包括旅行商问题的解决方案--一种非常慢的算法

• 画个图
  假设要画一个包含16格的网格(4*4)，且有以上5种不同的算法可供选择，使用第一种算法的时候操作数为4（log6=4），假设每秒可执行10次操作，那么需要0.4秒即可。那么如果要画1024个格子呢？这需要执行10次（log1024=10），也就是一秒就可以画完了。
  下图分别画出了绘制16个格子、绘制256个格子和绘制1024个格子在五种算法中分别消耗的时间。（这个例子是一个简化比较版本，实际情况可能个那个复杂）

绘制网格时间

大O表示法可以帮助我们快速分析算法的性能优劣，也可以帮助我们分析一个算法的实用性。