logo标签列表

什么是大O表示法？

computer-sciencebig-o
8

可能重复的问题:
Plain English explanation of Big O

我知道Big O符号用于评估算法的效率，但我不明白如何阅读Big O符号，以及算法的效率究竟有多高。有人能否解释一下Big O符号的基础知识呢？谢谢。

与Big O的简单英语解释相同。 - Matthew Flaschen
描述在大括号中的函数越强大，例如O(n^2)，算法就越复杂。假设n为3，那么O(n^2) = O(9)的复杂度比O(2n) = O(6)描述的算法更高。 - Willi Mentzel
3个回答
4
3

这个页面对我来说解释得非常清楚。

本质上，它是一种快速准确地评估算法性能特征的便捷方式。无论在最坏情况下或平均情况下算法运行的速度有多快。在最坏或平均情况下使用了多少空间。有时更有用的是算法在多个项目上的表现，这称为摊销分析。

符号的基本特征是随着 n 的增大而略去变得不相关的项。例如，当 n 变大时，n^2 + 2n 中的 2n 就变得不相关了。这将是 O(n^2)。

你建议的页面非常有帮助：我也一直在努力理解这个概念。 - MRN
1

大O符号描述了函数的极限行为。

在计算机科学中，通常使用它来展示算法随着数据集的增大而良好地扩展。例如，集合中的查找通常是不同的，并且根据集合类型使用大O符号进行描述。在.NET Framework中，Dictionary<T,U>具有一个Item属性，其文档如下：

获取或设置此属性的值接近于O(1)操作

这基本上意味着，无论您向集合中添加多少项，获取其中一项的时间都是恒定的。另一方面，List<T>将其Contains方法描述如下：

此方法执行线性搜索；因此，此方法是一个O(n)操作，其中n为Count。

这基本上意味着随着您添加更多的项，算法会以线性时间变慢。如果您放入1000个项目，则平均而言需要的时间大约是包含100个项目的列表的10倍，依此类推。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接