我正在为Java III课读一本教科书。我们正在阅读有关Big-Oh的内容,我对其正式定义有些困惑。
形式定义:“函数f(n)的阶数最多为g(n)-即f(n)= O(g(n))-如果存在正实数c和正整数N使得f (n)对于所有n> = N <= cg(n)。也就是说,当n足够大时,cg(n)是f(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)。”
“在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,则5n + 3 = 13而6n = 12,但是当n为3或更大时,5n + 3将始终小于或等于6n。
这就是我感到困惑的地方。 他们给了我另一个例子:
示例2:“让我们看一下4n ^ 2 + 50n-10 = O(n ^ 2)。很容易看到:4n ^ 2 + 50n-10 <= 4n ^ 2 + 50n对于任何n。因为50n < = 50n ^ 2对于n = 50,4n ^ 2 + 50n-10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2(n> = 50)。因此,对于c = 54和N = 50,我们表明4n ^ 2 + 50n- 10 = O(n ^ 2)。”
示例2:“让我们看一下4n ^ 2 + 50n-10 = O(n ^ 2)。很容易看到:4n ^ 2 + 50n-10 <= 4n ^ 2 + 50n对于任何n。因为50n < = 50n ^ 2对于n
= 50,4n ^ 2 + 50n-10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2(n> = 50)。因此,对于c = 54和N = 50,我们表明4n ^ 2 + 50n- 10 = O(n ^ 2)。”
该语句没有意义:n> = 50时为50n <= 50n ^ 2。
是不是n使50n小于50n ^ 2?不只是大于或等于50?他们为什么甚至提到50n <= 50n ^ 2?这与问题有什么关系?
同样,无论n是多少,4n ^ 2 + 50n-10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2对于n> = 50都是正确的。
世界上的拣选数字如何表明f(n)= O(g(n))?
请记住,您正在寻找“当n足够大时f(n)的上限”。因此,如果您可以证明对于大于 n的n值 ,f(n)小于或等于某些c g(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)也是如此。