Big Oh Notation - 正式定义

我正在阅读我的Java III课程的教科书。我们正在阅读关于Big-Oh的消息，我对它的正式定义有点困惑。（n） - 即f（n）= O（g（n）） - 如果一个正实数c和正整数N存在，使得对于所有n> = N，f（n）= cg（n）。也就是说，当n足够大时，cg（n）是f（n）的上限。Big Oh Notation - 正式定义

好的，这是有道理的。但是且慢，请继续阅读...这本书给了我这个例子：

“在段9.14，我们说，使用5N + 3个操作是O（n）的算法现在，我们可以展示。该5N + 3 = 为O（n）通过使用大哦的正式定义。

当n> = 3，5N + 3 < = 5N + N = 6N。因此，如果我们让F（N ）= 5n + 3，g（n）= n，c = 6，N = 3，我们已经表明当n≥3时或者5n + 3 = O（n）。也就是说，如果算法那么需要与时间成正比的关系，所以它是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 = 0（n^2）。“

这种说法没有任何意义：50N < = 50N^2对n> = 50

是不是任意n打算让50N小于50N^2？不只是大于或等于50？为什么他们甚至提到50n < = 50n^2？这与问题有什么关系？对于n> = 50，无论n是多少，4n^2 + 50n - 10 < = 4n^2 + 50n^2 = 54n^2将是真实的。

在世界上如何挑选数字表明f（n）= O（g（n））？

来源

2010-05-02 ShrimpCrackers

请记住，您正在寻找“当n足够大时f（n）的上限”。因此，如果对于n大于N的值可以证明f（n）小于或等于某个g（n），这意味着g（n）是f（n）的上界，而因此f（n）的复杂度为O（g（n））。

给出的例子旨在表明给定的函数f（n）对于任何n> 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）也是如此。

来源

2010-05-02 20:41:49

阿德里安谢谢你。通读你的解释让事情变得更加清晰。你应该当老师！ – ShrimpCrackers 2010-05-02 20:59:28

50n <= 50n^2 for n >= 50

因为如果n是50，那么50n与n^2相同，因为50 * 50等于50^2。

代n^2为50n，我们得到

n^2 <= 50n^2 for n >= 50

这是显而易见的。

来源

2010-05-02 19:58:16

也许我误解了这本书，但我读如果n是一定数字，它是50（50^2）不是50（50）。 50（50）与50（50^2）不一样。它从来没有说任何替代任何东西。 – ShrimpCrackers 2010-05-02 20:05:14

这只是简单的代数。我正在使用的唯一一个词就是左边的一个词。如果'n = 50'，我所做的只是表明'50n = n^2'。 – 2010-05-02 20:51:59

有关挑选数字的全部内容就是这样：使其更容易。因为你可以选择任何你喜欢的N和c数字，作者只是挑选了一些最容易看到的东西。这就是你也可以做的（当写考试等）。因此，尽管通常可以使用更小的N，但推理会变得有点困难（通常需要一些先前关于分析的知识 - 我们都已经学会了几年前的经验，x不会像增长那么快作为x^2 ...但是你想写下分析证明吗？）

保持简单，是消息:-)开始时习惯这一点有点奇怪。

来源

2010-05-02 20:30:13

谢谢。我明白我可以选择任何数字。然而，在我给出的例子中，作者声称任何数字> = 50使得陈述50n <= 50n^2成立。这是如此真实？任何n都会使得这个陈述是真实的，不仅仅是数字> = 50. 50（50）和50（50^2）不是一回事，对吗？ – ShrimpCrackers 2010-05-02 20:42:28

另外，在这个例子中，数字似乎来自无处。例如：作者试图显示4n^2 + 50n - 10 = O（n^2）。后来他写道，4n^2 + 50n - 10 <= 4n^2 + 50n^2 = 54n^2。在右侧，他为什么突然决定在50前面贴上n^2？为什么-10会在RHS上消失？ – ShrimpCrackers 2010-05-02 20:43:03

1 .:作者可能认为：对于n = 50，'50n <= 50n^2'与'50 * 50 <= 50 * 50 * 50'相同，在这种情况下，它非常容易看到（但你当然是对的，对于任何积极的n也很容易看出）。 – 2010-05-02 20:49:56

当n> = 50时，他们说50n < = 50n^2的原因可能是，如果n小于1，比n^2 < n。当然，如果n是正整数，那么是50n < = 50n^2。在这种情况下，似乎假设n是一个正整数，虽然他们给出的形式定义没有明确说明。

我可以看到，为什么说50N < = 50N^2对n> = 50似乎有点傻。但这仍然是事实。本书不说50n < = 50n^2只适用于n> = 50;那会是错误的。

打个比方，如果我说“我所有的兄弟姐妹说英语”，这将是真实的，即使有很多人谁讲英语谁都不是我的兄弟姐妹。

关于证明，我们可以把它拆分成不同的语句。

(1): 4n^2 + 50n - 10 <= 4n^2 + 50n (for all n) 
(2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50) 
(3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50) 
(4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50 
(5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54, 
      the statement f(n) <= c g(n) for all n >= N is true 
(6): Therefore, by definition 4n^2 + 50n - 10=O(n^2).

应该清楚的是，这些陈述是真实的，无论其自身（1,2,3），或在以前的声明的结果。

来源

2010-05-02 21:28:29 dan

形式定义：

F（N）= O（G（N））指存在C> 0，且n ，使得对于任意的n> = N F（N ）< = C * G（n）的
F（N）= O（G（N））用于任何C> 0存在n个，使得对于任意的n> = N F（N ）< = c * g（n）

正如你可以注意到略有不同:)

来源

2010-05-03 07:33:27

Big Oh Notation - 正式定义

回答

相关问题