大Ｏ表示法

大Ｏ表示法？？？这是什么东西？？

大Ｏ表示法其实并没有多么高大上，而是一种特殊的表示法，指出了算法的速度有多快。这种表示法简单易懂，非常明了，所以应用广泛。

举个例子，就如我上一篇博客中提到的二分查找（https://blog.csdn.net/qq_45835827/article/details/104651718）。如果用大Ｏ表示法来分别表示简单查找和二分查找的速度为：
简单查找：O(n)
二分查找：O(log₂n)
这就是大Ｏ表示法，前面的Ｏ有点大。

因为在很多时候，如果只是告诉你算法花了多长时间是没有用的，而是需要知道运行时间如何随list的增长而增长。大Ｏ表示法的用武之地就在于此。也就是之前所说的，大Ｏ表示法指出了算法的速度有多快。

下面给大家介绍一些常见的大Ｏ运行时间

• O(log₂n)，对数时间，例如：二分查找。
• O(log n)，线性时间，例如：简单查找。
• O(n * log₂n)，例如：快速排序（可以参考我的另外一篇博客）。
• O(log n²)例如：选择排序（可以参考我的另外一篇博客）。
• O(log n!)例如：用于旅行商问题。

大家可能也注意到了一点，大Ｏ表示法指出了最糟情况下的运行时间。怎么去理解这个性质呢？其实就是说该算法最糟运行的时间大Ｏ表示法所指代的时间，这是一个保证。比如说，小明心里想的数字为50，结果大红一次就猜中了，这就是最佳情况。所以还应考虑平均情况（在我后面的博客有介绍）。

另外，在实际的应用中，我们很难将运行时间直接转换为操作数（即大Ｏ后面括号里表示的速度）。前面介绍的都是比较简单的例子供大家参考理解。

最后归纳总结一下从大Ｏ表示法中获得的理解。

• 算法的速度并非指的时间，而是操作数的增速。
• 谈论算法的速度的时候，我们指的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示
• 当搜索的元素越多的时候，算法速度的比较就越明显。
• 算法的运行时间不以秒为单位，而是从其增速的角度来度量的。

本博客所有内容均整理自《算法图鉴》，这篇博客也作为自己的学习笔记，欢迎大家交流讨论。

最后

以上就是复杂摩托为你收集整理的大Ｏ表示法的全部内容，希望文章能够帮你解决大Ｏ表示法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。