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 - 正式定義

回答

相關問題