当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - Big O Notation: Definition

问题描述:

I've been watching MIT lectures for the algorithms course and the definition for the Big O notation says

f(n) = O(g(n)) such that for some constants c and n0

0 < f(n) < c.g(n) for all n>n0

Then the instructor proceeded to give an example,

2n2=O(n3)

Now I get that Big O gives the upper bound on the function but I am confused as to what exactly does the function f(n) correspond to here? What is its significance? As per my understanding goes, g(n) is the function representing the algorithm we are trying to analyse, but what is the purpose of f(n) or as in the example 2n2?

Need some clarification on this, I've been stuck here for hours.

网友答案:

In the formal definition of big-O notation, the functions f(n) and g(n) are placeholders for other functions, the same way that, say, in the quadratic formula, the letters a, b, and c are placeholders for the actual coefficients in the quadratic equation.

In your example, the instructor was talking about how 2n2 = O(n3). You have a formal definition that talks about what it means, in general, for f(n) = O(g(n)) to be true. So let's pattern-match that against the math above. It looks like f(n) is the thing on the left and g(n) is the thing on the right, so in this example f(n) = 2n2 and g(n) = n3.

The previous paragraph gives a superficial explanation of what f(n) and g(n) are by just looking at one example, but it's better to talk about what they really mean. Mathematically, f(n) and g(n) really can be any functions you'd like, but typically when you're using big-O notation in the context of the analysis of algorithms, you'll usually let f(n) be the true amount of work done by the algorithm in question (or its runtime, or its space usage, or really just about anything else) and will pick g(n) to be some "nice" function that's easier to reason about. For example, it might be the case that some function you're analyzing has a true runtime, as a function of n, as 16n3 - 2n2 - 9n + 137. That would be your function f(n). Since the whole point behind big-O notation is to be able to (mathematically rigorously and safely) discard constant factors and low-order terms, we'll try to pick a g(n) that grows at the same rate as f(n) but is easier to reason about - say, g(n) = n3. So now we can try to determine whether f(n) = O(g(n)) by seeing whether we can find the constants c and n0 talked about in the formal definition of big-O notation.

So to recap:

  • f(n) and g(n) in the definition given are just placeholders for other functions.
  • In practical usage, f(n) will be the true runtime of the algorithm in question, and g(n) will be something a lot simpler that grows at the same rate.
网友答案:

f(n) is the function that gives you the exact values of the thing you are trying to measure (be that time, number of processor instructions, number of iterations steps, amount of memory used, whatever).

g(n) is another function that approximates the growth of f(n).

In the usual case you don't really know f(n) or it's really hard to compute. For example for time it depends on the processor speed, memory access patterns, system load, compiler optimizations and other. g(n) is usually really simple and it's easier to understand if f(n) = O(N) that if you double n you will roughly double the runtime, in the worst case. Since it's an upper bound g(n) doesn't have to be the minimum, but usually people try to avoid inflating it if it's not necessary. In your example O(n^3) is an upper bound for 2n^2, but so is O(n^2) and O(n!).

分享给朋友:
您可能感兴趣的文章:
随机阅读: