一尘不染

大哦符号-正式定义

algorithm

我正在为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)。”

好的,这对我来说很有意义。 他们的意思是,如果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)。”

该语句没有意义: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))?


阅读 334

收藏
2020-07-28

共1个答案

一尘不染

请记住,您正在寻找“当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)也是如此。

2020-07-28