我正在为我的Java III课阅读一本教科书.我们正在阅读关于Big-Oh的内容,我对其正式定义感到有些困惑.
形式定义:"函数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).我们现在可以通过使用Big Oh的形式定义来显示5n + 3 = O(n).
当n> = 3时,5n + 3 <= 5n + n = 6n.因此,如果我们让f(n)= 5n + 3,g(n)= n,c = 6,N = 3,我们已经证明了对于n> = 3,f(n)<= 6 g(n),或5n + 3 = O(n).也就是说,如果算法需要与5n + 3成正比的时间,则为O(n)."
好的,这种对我来说很有意义.他们说如果n = 3或更大,5n + 3比n小于3所花费的时间少 - 因此5n + n = 6n - 对吗？有意义,因为如果n是2,5 n + 3 = 13而6n = 12但是当n是3或更大时5n + 3总是小于或等于6n.
这是我感到困惑的地方.他们给我另一个例子:
例2:"让我们看一下4n ^ 2 + 50n - 10 = O(n ^ 2).很容易看出:对于任何n,4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n.自50n <对于n,= 50n ^ 2
对于n> = 50,= 50,4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2.因此,当c = 54且N = 50时,我们已经证明4n ^ 2 + 50n - 10 = O(n ^ 2)."
这句话没有意义:对于n> = 50,50n <= 50n ^ 2.
是不是要让50n小于50n ^ 2？不只是大于或等于50？为什么他们甚至提到50n <= 50n ^ 2？这与问题有什么关系？
而且,无论n是多少,对于n> = 50,4n ^ 2 + 50n-10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2都是正确的.
挑选数字在世界上如何显示f(n)= O(g(n))？
请记住,当n足够大时,你正在寻找"f(n)的上限." 因此,如果你可以证明f(n)小于或等于某个c g(n)的n值大于N,这意味着c g(n)是f(n)和f的上界( n)因此复杂度为O(g(n)).
给出的例子旨在表明,对于任何n> N,给定函数f(n)永远不会超过c*g(n).通过操纵初始上界,可以更简单地表达它(如果4n ^ 2 + 50n是f(n)的上界,那么4n ^ 2 + 50n ^ 2,它等于54n ^ 2,这就是你的54*g(n),其中c = 54,g(n)= n ^ 2),作者可以证明f(n)受c*g(n)的约束,其具有复杂度O(g(n)),因此f(n)也是如此.