blocks|key|5006527|text|在数学、计算机科学和相关领域中，大O表示法描述了当论点趋向于某一特定值或无穷大时，函数的极限行为，通常用更简单的函数来表示。|type|blockquote|depth|inlineStyleRanges|entityRanges|data|5006528|这就是他们给出的寻找这个值的过程的名称。你可以在维基上读到更多关于它的信息。|unstyled|offset|length|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Big_O_notation^0|0|O|2|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|O|8|@]|9|@$E|P|F|Q|1|R]]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

<blockquote>
 In mathematics, computer science, and
 related fields, big-O notation
 describes the limiting behavior of a
 function when the argument tends
 towards a particular value or
 infinity, usually in terms of simpler
 functions.
</blockquote>

That is the name they gave the process of finding that value. You can read more about it on the <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow">wiki</a>

blocks|key|1267619|text|在数学中，大O是渐近上界的表示法。Big-O函数(用适当的值填充未指定的常量)总是至少与"real“函数一样大。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1267620|也有渐近下界和紧界的符号。在紧界情况下，在常数选择不同的情况下，相同的渐近公式既是“实”函数的上界，也是下界。这就是所谓的“在一个不变的因素内”。|1267621|完整的渐近符号列在这里..。|1267622|http://en.wikipedia.org/wiki/Big_O_notation#Family_的_Bachmann.E2.80.93Landau_符号|offset|length|1267623|函数的上限很自然地与最坏的内存或时间要求相匹配，而最坏的性能函数的下界往往会给出许多比最坏的结果更好的结果(这是一种最好的情况-最坏的-不匹配)。类似地，下限很自然地符合最好的内存或时间要求，尽管对于算法，我们对此不太感兴趣。|1267624|一些算法教科书(特别是Cormen等人)经常使用严格的界限。|1267625|但事实证明，最坏情况的下限可能是有用的。我最近问了这个问题..。|1267626|为什么我会关心最坏情况下界的渐近增长？|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations|1|https://softwareengineering.stackexchange.com/questions/74421/why-would-i-care-about-the-asymptotic-growth-of-the-lower-bound-of-the-worst-case^0|0|0|0|0|27|0|0|0|0|0|0|J|1^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|13|8|@]|9|@$H|14|I|15|1|16]]|A|$]]|$1|J|3|K|5|6|7|17|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|18|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|19|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1A|8|@]|9|@$H|1B|I|1C|1|1D]]|A|$]]]|R|$S|$5|T|U|V|A|$W|X]]|Y|$5|T|U|V|A|$W|Z]]]]

In mathematics, Big O is the notation for an asymptotic upper bound. The Big-O function (with the unspecified constants filled in with appropriate values) is always at least as large as the "real" function.

There are also notations for the asymptotic lower bound, and for a tight bound. In the tight bound case, with different selections of constants, the same asymptotic formula is both an upper bound and a lower bound of the "real" function. This is known as being "within a constant factor".

The complete set of asymptotic notations is listed here...

<a href="http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations</a>

The upper bound of a function naturally matches the worst-case memory or time requirements, whereas the lower bound of the worst-case performance function tends to give lots of better-than-worst-case results (it's a kind of best-cases-of-the-worst-cases mismatch). Similarly, the lower bound naturally matches the best-case memory or time requirements, though for algorithms we're less often interested in that.

Some algorithms text books (notably Cormen et al.) use tight bounds a lot.

It turns out that the lower bound of the worst case can be useful, though. I asked this question recently...

<a href="https://softwareengineering.stackexchange.com/questions/74421/why-would-i-care-about-the-asymptotic-growth-of-the-lower-bound-of-the-worst-case">Why would I care about the asymptotic growth of the lower bound of the worst case time/space?</a>

blocks|key|5006479|text|因为这正是设计要找出的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|4|5|6|7|C|8|@]|9|@]|A|$]]]|B|$]]

Because that is exactly what it is designed to find out.

blocks|key|5006677|text|主要是因为最坏的情况和最普通的情况是大多数人所关心的--我真的能期待什么，以及最坏的情况会发生什么？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5006678|最好的案例确实有一些真正的用途--例如，我看到人们花了很多时间试图找到更好的算法，如果他们花了10分钟思考最好的情况，他们就会意识到他们已经做到了(至少从渐近复杂性的角度来看)--这是他们所能期望的。|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|E|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|F|8|@]|9|@]|A|$]]]|D|$]]

Mostly because worst case and average case are the ones most people care about -- what can I really expect, and what's the worst that could happen?

The best case does have some real uses though -- for example, I've seen people waste a lot of time trying to find significantly better algorithms in cases that if they'd spent 10 minutes thinking about the best case, they'd have realized that what they had was already (at least from an asymptotic complexity perspective) as good as they could hope for.

blocks|key|5006698|text|因为最坏的情况比最好的情况更常见。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5006699|通常，当您考虑算法的复杂性时，您不会遇到对输入做出太多假设的情况。因此，您必须考虑平均情况(在任意输入的大量运行中估计性能)或最坏情况(估计处理任意输入所需的时间)。最好的案子？如果你幸运的话，很少有人会关心你的程序会运行得非常快。|5006700|当然，我们可以想象不同的情况。例如，如果列表已经排序，则臭名昭著的Bubblesort的最佳情况是O(N)。如果您有一个列表，您知道它将几乎被排序(例如，以前排序的列表对某些元素做了一些小的更改)，您可以确信Bubblesorting它将接近最佳的案例性能。但是，您永远不会使用Bubblesort作为一般类型，它将接受任意数量的任意洗牌元素。|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|H|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|I|8|@]|9|@]|A|$]]]|F|$]]

Because it is much much much more common to care about the worst case than the best case.

Generally, when you're thinking about the complexity of your algorithm, you're not in a situation where you can make too many assumptions about the input. Therefore, you will have to consider the average case (to estimate performance over large numbers of runs with arbitrary input) or the worst case (to estimate just how long it might take to process arbitrary input). Best case? It's rare to care that your program might run really quickly if you're lucky.

Of course, one can imagine different situations. For example, the best case for the infamous Bubblesort is O(N) if the list was already sorted. If you have a list which you know will be almost sorted (e.g., a previously sorted list that has had some small changes made to some elements), you can be confident that Bubblesorting it will be close to best case performance. But you would never use a Bubblesort for a general sort that was going to take an arbitrary number of arbitrarily shuffled elements.

Why is big O most commonly associated with worst and average case complexties of a function

BIG O - Algorithm Case Analysis

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

为什么大O最常与函数的最坏和平均情况的复杂性相关联？

问大O算法案例分析
EN

回答 5

Software Engineering用户

Software Engineering用户

Software Engineering用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问大O算法案例分析EN

回答 5

Software Engineering用户

Software Engineering用户

Software Engineering用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问大O算法案例分析
EN