大哦符号 - 正式定义 [英] Big Oh Notation - formal definition
问题描述
我在读一本教科书，现在我的Java III级。我们正在阅读有关大哦，我用它正式的定义有点糊涂了。
正式定义：一个函数f（n）是订货最多G（N） - 即f（N）= O（G（N）） - 如果一个正实数c和正整数N，存在使得f（n）的与所述; = CG（n）的对所有的n> = N。即，CG（n）是一个上界F（N）当n是足够大的
好吧，这是有道理的。但是且慢，请继续阅读...这本书给了我这个例子：
在段9.14，我们说的 算法，其使用5N + 3的操作 为O（n）。现在，我们可以证明5N + 3 = O（n）的使用的正式定义 大哦。
当n> = 3，5N + 3'= 5N + N = 6N。 因此，如果我们令f（n）的= 5N + 3克（正）= N，C = 6，N = 3，我们已经表明， F（N）＆LT; = 6克（N）的N> = 3，或5N + 3 = 上）。也就是说，如果一个算法 需要时间成正比 5N + 3，这是O（n）。
好，这种对我来说很有意义。 他们说，如果n = 3或更大，5N + 3时间低于当n小于3 - 从而5N + N = 6N - 右是有道理的，因为如果n为2 ，5N + 3 = 13，而6n个= 12，但是当n为3或更大5N + 3将总是小于或等于6N
这里就是我弄糊涂他们给了我另外一个例子：
例2：让我们表明，4N ^ 2 + 50N - 10 =为O（n ^ 2）。这是很容易看出：4N ^ 2 + 50N - 10 LT = 4N ^ 2 + 50N 对任意n。由于50N＆LT; = n个50N ^ 2
= 50，4N ^ 2 + 50N - 10＆其中; = 4N ^ 2 + 50N ^ 2 = 54N ^ 2对于n> = 50。因此，采用c = 54和N = 50，我们已经表明，4N ^ 2 + 50N - 10 =为O（n ^ 2）
。
该声明没有任何意义：50N＆LT; = n个50N ^ 2> = 50
是不是任意n将会创造出50N小于50N ^ 2？不仅仅是大于或等于50更大？为什么他们甚至提到50N＆LT; = 50N ^ 2？这是什么都与这个问题呢？
此外，4N ^ 2 + 50N - 10 LT = 4N ^ 2 + 50N ^ 2 = 54N ^ 2的N> = 50将不管n是真的。
和如何在世界上没有挑选号码显示，F（N）= O（G（N））？
请帮助我了解！ ：（
请记住，你要寻找的一个上限F（N）时，n是足够大的。因此，如果能证明F（N）小于或等于某些C * G（N）对于n比N个值以上，这意味着C *克（n）是一个上限对于f（n）和因此，F（N）的复杂度为O（G（N））。
给出意在表明给定函数f（n）的可以永远超C * G（N）的任意n> N的例子通过操纵一个初始的上限，因此它可以是前pressed更多简单地（如果4N ^ 2 + 50N是上限F（N），则这样是4N ^ 2 + 50N ^ 2，它等于54N ^ 2，成为你54 *克（n），其中C = 54和G（N）= N ^ 2），作者可以显示使f（n）被以c * G（N），其具有复杂度为O（克（n括住）），因此，这样做F（N）。
I'm reading a textbook right now for my Java III class. We're reading about Big-Oh and I'm a little confused by its formal definition.
Formal Definition: "A function f(n) is of order at most g(n) - that is, f(n) = O(g(n)) - if a positive real number c and positive integer N exist such that f(n) <= c g(n) for all n >= N. That is, c g(n) is an upper bound on f(n) when n is sufficiently large."
Ok, that makes sense. But hold on, keep reading...the book gave me this example:
"In segment 9.14, we said that an algorithm that uses 5n + 3 operations is O(n). We now can show that 5n + 3 = O(n) by using the formal definition of Big Oh.
When n >= 3, 5n + 3 <= 5n + n = 6n. Thus, if we let f(n) = 5n + 3, g(n) = n, c = 6, N = 3, we have shown that f(n) <= 6 g(n) for n >= 3, or 5n + 3 = O(n). That is, if an algorithm requires time directly proportional to 5n + 3, it is O(n)."
Ok, this kind of makes sense to me. They're saying that if n = 3 or greater, 5n + 3 takes less time than if n was less than 3 - thus 5n + n = 6n - right? Makes sense, since if n was 2, 5n + 3 = 13 while 6n = 12 but when n is 3 or greater 5n + 3 will always be less than or equal to 6n.
Here's where I get confused. They give me another example:
Example 2: "Let's show that 4n^2 + 50n - 10 = O(n^2). It is easy to see that: 4n^2 + 50n - 10 <= 4n^2 + 50n for any n. Since 50n <= 50n^2 for n
= 50, 4n^2 + 50n - 10 <= 4n^2 + 50n^2 = 54n^2 for n >= 50. Thus, with c = 54 and N = 50, we have shown that 4n^2 + 50n - 10 = O(n^2)."
This statement doesn't make sense: 50n <= 50n^2 for n >= 50.
Isn't any n going to make the 50n less than 50n^2? Not just greater than or equal to 50? Why did they even mention that 50n <= 50n^2? What does that have to do with the problem?
Also, 4n^2 + 50n - 10 <= 4n^2 + 50n^2 = 54n^2 for n >= 50 is going to be true no matter what n is.
And how in the world does picking numbers show that f(n) = O(g(n))?
Please help me understand! :(
Keep in mind that you're looking for "an upper bound on f(n) when n is sufficiently large." Thus, if you can show that f(n) is less than or equal to some c*g(n) for values of n greater than N, this means c*g(n) is an upper bound for f(n) and f(n)'s complexity is therefore O(g(n)).
The examples given are intended to show that the given function f(n) can never grow beyond c*g(n) for any n > N. By manipulating an initial upper bound so it can be expressed more simply (if 4n^2 + 50n is an upper bound on f(n) then so is 4n^2 + 50n^2, which is equal to 54n^2, which becomes your 54*g(n) where c = 54 and g(n) = n^2), the authors can show that f(n) is bounded by c*g(n), which has complexity O(g(n)) and therefore so does f(n).
这篇关于大哦符号 - 正式定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
