问题描述
我在读一本教科书,现在我的Java III级。我们正在阅读有关大哦,我用它正式的定义有点糊涂了。
正式定义:一个函数f(n)是订货最多G(N) - 即f(N)= O(G(N)) - 如果一个正实数c和正整数N,存在使得f(n)的与所述; = CG(n)的对所有的n> = N。即,CG(n)是一个上界F(N)当n是足够大的
好吧,这是有道理的。但是且慢,请继续阅读...这本书给了我这个例子:
好,这种对我来说很有意义。 他们说,如果n = 3或更大,5N + 3时间低于当n小于3 - 从而5N + N = 6N - 右是有道理的,因为如果n为2 ,5N + 3 = 13,而6n个= 12,但是当n为3或更大5N + 3将总是小于或等于6N
这里就是我弄糊涂他们给了我另外一个例子:
该声明没有任何意义:50N< = n个50N ^ 2> = 50
是不是任意n将会创造出50N小于50N ^ 2?不仅仅是大于或等于50更大?为什么他们甚至提到50N< = 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:
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:
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).
这篇关于大哦符号 - 正式定义的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!