Does Big O Measure Memory Requirments Or Just Spee

问题:

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

回答1:

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.

回答2:

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.

回答3:

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).

回答4:

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.

回答5:

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.

回答6:

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.

回答7:

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 in O(N^2) time. Another algorithm may run on O(N^2) processors in O(N) time.

Related questions

• Big-oh vs big-theta

See also

• Wikipedia/Big O Notation

回答8:

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.