大O符号数学证明 [英] Big O notation mathematical proof
问题描述
我正试图了解Big O的确切含义.通过对SO中类似问题的回答，我从字面意义和实践意义上理解了它.但是答案无法解释，我无法理解的是其背后的数学基础.正式定义指出
当且仅当存在两个常数c，n0>时，函数T(n)才是f(n)的Big-O表示法.0这样对于所有n＞ ＝ n0，T(n)＜＝ c * f(n). 我在某种程度上直观地了解到，该方程试图根据某种意义上具有较高斜率的函数(函数f(n)的高端)来计算上限.我知道我的理解是模糊的.因此，有人可以解释Big-O表示法的数学基础/表示形式.
首先让我说，如果 g(n)是 n 的函数，则 O(g(n))是所有函数 f(n)的集合，使得存在常数c，N> 0使得f(n)<; = cg(n)表示所有n> = N .
如果准确地分析算法 ，那么就会得出输入大小 n 的函数，例如 f(n)，这可能是 n 中某些复杂的烦人的多项式表达式(或涉及指数的复杂表达式).
例如，可能发现在给定输入大小为 n 的情况下，一种算法完全具有 f(n)= 2n ^ 2 + 3n + 1 指令.但是我们并不真正在意 3n + 1 部分.如果 n 变得很大，则 f 的 n ^ 2 项将主导低阶项.例如，对于 n = 100 ，我们已经发现 2 * 100 ^ 2 比 3 * 100 +1 重要得多./p>
因此，为了使这个概念更严格，我们想说" f(n)在最坏的情况下像n ^ 2一样增长" .用数学符号表示: f(n)是O(n ^ 2)的元素.现在，正如您在问题中所述，要实际证明f(n)是O(n ^ 2)的元素，我们需要找到常数c和N，使得对于所有n> = N，我们都有f(n)< = cn ^ 2.因此，如果我们尝试c = 3，那么我们得到的不等式f(n)< = 3 * n ^ 2，并且如果您代数运算，那么对于所有n> = 5来说，这都是成立的.因此，我们的c = 3，我们的N = 5.实际上，f(n)在最坏的情况下会像n ^ 2一样增长.
但是请注意，单词最糟糕的情况是" .说"f(n)增长成..." 是错误的，相反，我们说" f(n)增长成......"../p>
再举一个例子，请考虑我们的 f(n)= 2n ^ 2 + 3n + 1 .我认为 f(n)不是O(n)的元素.为了实际证明这是正确的，我们需要证明对于所有c，N> 0，都存在一个n> = N，使得f(n)> cn.好，当且仅当2n ^ 2 +(3-c)n + 1> 0时，f(n)> cn为真，这对于足够大的n> = N(无论N是多少)都成立.我会让你弄清楚细节.这表明 f(n)的增长速度比线性增长慢.
还有另一个例子，我们的 f(n)= 2n ^ 2 + 3n + 1 :可以证明f(n)是O(n ^ 3)的元素.那样做吧?我们需要找到c，N> 0，使得对于所有n> = N，f(n)< = cn ^ 3.好吧，尝试c = 1；然后经过一些代数运算后，您会发现对于N = 4，这是正确的.这保证了"f(n)会在最坏的情况下如...般增长"；如果您可以证明函数f在某个big-O中，则可能是其中一部分的更好的big-O".
作为最后的练习，请证明O(1)是O(n)的 proper 子集，这是O(n ^ 2)的 proper 子集，它是O(n ^ 3)的正确子集，它是O(n ^ 4)的正确子集，...
I am trying to understand what exactly Big O notation is. I understand it in the literal and practical sense by going through the answers of similar questions in SO. But what the answers don't explain and i fail to understand is the mathematical basis behind it. The formal definition states that
A function T(n) is the Big-O notation of f(n), if and only if there exist two constants c, n0 > 0 such that
T(n) <= c * f(n) for all n >= n0.
I understand intuitively to some extent that this equation tries to calculate the upper bound in terms of some function which has higher slope in the sense, something in the higher end to the function f(n). I know my understanding is vague. So can someone please explain the mathmatical basis/representations of Big-O notation.
First let me just say that if g(n) is a function of n, then O(g(n)) is the set of all functions f(n) such that there exist constants c,N>0 such that f(n) <= cg(n) for all n >= N.
If one analyzes an algorithm exactly, then one comes up with a function of the input size n, say f(n), which might be some complicated annoying polynomial expression in n (or a complicated expression involving an exponential).
For example, one might find that an algorithm, given an input size of n, has exactly f(n) = 2n^2 +3n + 1 instructions. But we don't really care about the 3n + 1 part. If n gets very large, the n^2 term of f will dominate the lower-order terms. For instance, for n=100 we already find that 2*100^2 is a lot more significant than 3*100 + 1.
So, to make this idea more rigorous, we'd like to say that "f(n) grows at worst like n^2". In mathematical notation: f(n) is an element of O(n^2). Now as you've stated in your question, to actually prove that f(n) is an element of O(n^2), we need to find constants c and N such that for all n >= N we have f(n) <= cn^2. So if we try c=3, then we get the inequality f(n) <= 3*n^2, and if you play around algebraically then you'll find that for all n >= 5 this holds true. So our c=3 and our N=5. Indeed, f(n) grows at worst like n^2.
Notice however the words "at worst like". It would be wrong to say "f(n) grows like ...", instead we say "f(n) grows at worst like...".
To give you another example, consider our f(n) = 2n^2 + 3n + 1 again. My claim is that f(n) is not an element of O(n). To actually show that this is true, we need to show that for all c,N>0 there exists an n>=N such that f(n) > cn. Well, f(n) > cn is true if and only if 2n^2 + (3-c)n + 1 > 0, which is true for for sufficiently large n>=N (no matter what N is), of which I'll let you work out the details. This shows that f(n) grows at a worse rate than linear.
Yet another example with our f(n) = 2n^2 + 3n + 1: It can be shown that f(n) is an element of O(n^3). Let's do that, shall we? We need to find c,N>0 such that f(n) <= cn^3 for all n>=N. Well, try c=1; then after some algebra you can find that this is true for N=4. This warrants the "f(n) grows at worst like ..." sentiment; if you can show that your function f is in some big-O, then there might a "better big-O" for which it is part of.
As a final exercise, show that O(1) is a proper subset of O(n), which is a proper subset of O(n^2), which is a proper subset of O(n^3), which is a proper subset of O(n^4), ...
这篇关于大O符号数学证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
