Big O 测量内存需求还是仅测量速度？
我经常在这里人们谈论 Big O，它衡量算法之间的对比，
这是否衡量时钟周期或空间要求。
如果人们想根据内存使用情况对比算法，他们会使用什么衡量标准
I often here people talk about Big O which measures algorithms against each other
Does this measure clock cycles or space requirements.
If people want to contrast algorithms based on memory usage what measure would they use
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
Big O 和其他用于衡量事物的增长。
当有人说某个东西是
O(N)时，那么该东西的增长速度不会比线性速度快。如果某物是Ω(N^2)，那么该物的增长速度不会慢于二次率。当某个东西是θ(2^N)时，那么这个东西就会以指数速度增长。那东西可能是算法的时间要求。它也可以是算法的空间，即内存需求。它也可以是几乎任何东西，与空间和时间无关。
例如，一些大规模并行算法通常会衡量其可以运行的处理器数量的可扩展性。特定算法可以在
O(N)处理器上以O(N^2)时间运行。另一种算法可能在O(N^2)处理器上以O(N)时间运行。相关问题
另请参阅
Big O and others are used to measure the growth of something.
When someone says that something is
O(N), then that thing grows no faster than linear rate. If something isΩ(N^2), then that thing grows no slower than quadratic rate. When something isΘ(2^N), then that thing grows at an exponential rate.What that thing is can be the time requirement for an algorithm. It can also be the space i.e. memory requirement for an algorithm. It can also be pretty much anything, related to neither space nor time.
For example, some massively parallel algorithms often measure the scalability in the number of processors that it can run on. A particular algorithm may run on
O(N)processors inO(N^2)time. Another algorithm may run onO(N^2)processors inO(N)time.Related questions
See also
虽然通常算法会按时间竞争，但我通常会假设任何 O 语句都是时间。然而，比较空间也是完全有效的。 O 可用于任何测量 - 我们通常只使用速度，因为它通常是最重要的。
While normally algorithms compete on time, then I would normally assume that any O statement was time. However, it's perfectly valid to also compare space. O can be used for any measurement- we just normally use speed because it's normally the most important.
如果有人说“这个算法运行时间为 O(n)”，他指的是速度。如果有人说“这个算法在 O(n) 空间中运行”，他正在谈论内存。
如果他只是说“这个算法是 O(n)”，那么他通常是在谈论速度（尽管如果他在讨论内存时这么说，那么他可能是在谈论内存）。
如果您不确定某人在谈论哪一个，请询问他。
If someone says "This algorithm runs in O(n) time", he's talking about speed. If someone says "This algorithm runs in O(n) space", he's talking about memory.
If he just says "This algorithm is O(n)", he's usually talking about speed (though if he says it during a discussion about memory, he's probably talking about memory).
If you're not sure which one someone's talking about, ask him.
简短的回答：你有“空间中的大O”和“时间中的大O”。
长答案：大O只是一个符号，你可以在任何你想要的上下文中使用它。
Short answer : you have 'Big O in space" and "Big O in time".
Long answer: Big O is just a notation, you can use it in whatever context you want.
大O只是一个数学工具，可以用来描述任何函数。通常人们用它来描述速度，但它也可以用来描述内存使用情况。
另外，当我们使用 Big O 表示时间时，我们通常不会直接谈论时钟周期。相反，我们计算“基本操作”（隐式假设需要恒定数量的周期）。
Big O is just a mathematical tool that can be used to describe any function. Usually people use it to describe speed, but it can just as well be used to describe memory usage.
Also, when we use Big O for time, we're usually not talking directly about clock cycles. Instead, we count "basic operations" (that are implicitly assumed to take a constant number of cycles).
通常是操作数量，也就是速度。通常，算法在速度上的差异比在内存使用上的差异更大。但是，在适当的情况下，您将看到用于内存使用的 O() 表示法。
Typically it's the number of operations, which translates to speed. Usually, algorithms differ more in speed than in memory usage. However, you will see the O() notation used for memory use, when appropriate.
Big O 实际上只是基于输入增长的复杂性增长的衡量标准。
两个都是 O(n) 的算法可能会在截然不同的时间执行，但它们的增长与输入的增长呈线性关系。
Big O is really just a measure of the growth of complexity based on growth of input.
Two algorithms with are both O(n) may execute in vastly different times but their grown is linear with relation to the growth of the input.
Big-O 可用于描述任意两个量之间的关系。尽管它通常仅用于计算机科学，但该概念也可能适用于物理学等其他领域。例如，无论天线形状如何，为了在一定距离处产生单位强度的信号，必须输入给定尺寸的天线的功率量为 O(d^2)。如果天线的尺寸相对于距离较大，则所需强度的增加可能是线性的，甚至是次线性的，而不是二次项，但随着距离变大，二次项将占主导地位。
Big-O can be used to describe the relationship between any two quantities. Although it is generally only used in computer science, the concept may also be applicable in other fields like physics. For example, the amount of power that must be put into an antenna of a given size to yield a unit-strength signal at some distance is O(d^2), regardless of the antenna shape. If the size of the antenna is large relative to the distance, the increase in strength required may be linear or even sub-linear rather than quadratic, but as the distance gets larger, the quadratic term will dominate.