證明/反駁BigO和BigTheta

Question

我有問題完全理解如何證明以下某些語句。

例如我有一個聲明：n^2logn = O(n^2)。 如果我錯了，請糾正我，但是這表明n^2是n^2logn的bigO。這意味着n^2的增長速度快於n^2logn。現在我們將如何去證明這一點？我認爲我需要通過我嘗試使用的感應來使用證明，但是在這個過程中被卡住了。我能否重寫這個聲明爲n^2logn <= n^2？

是否有可能使用歸納來反證某些事物？例如，反駁n!=O(n^n)。或者僅僅通過顯示一個任意值來反駁這個陳述是有效的）比方說大於2）不滿足陳述？

最後，爲了清楚起見，bigTheta指出，增長正確時方程是等價的？

Answer 1

根據權利要求n^2logn是O(n^2)直觀地意味着是n^2logn生長至多一樣快n^2 -asymptotically（這種說法是錯誤的）。

按照定義，這意味着有某種常量C，N，使得對於每個n>N：c*n^2logn <= n^2

駁它是由矛盾非常簡單。
假設（錯誤地）的說法是真實的，並讓N,c是我們的常數：

c*n^2logn <= n^2 
c*logn <= 1 
logn <= 1/c 

但c是恆定的，並有一些n>N這樣logn > 1/c - 矛盾。

您可以通過誘導出別的東西，例如反駁 - 如果你通過歸納表明n! < n^n - 你居然反駁索賠n! = n^n

關於大THETA，我試圖在細節來說明這個問題線程Big Theta Notation - what exactly does big Theta represent?

Answer 2

我現在正在學習算法，所以我可以回答其中的一些問題，當我回家時，我可以回答其他問題，看看我的筆記。

例如我有一個聲明：n^2logn = O（n^2）。如果我錯了，請糾正我，但是這表明n^2是n^2logn的bigO。這意味着n^2比n^2logn增長更快。

你是對的。

現在我們將如何去證明這一點？我認爲我需要通過我嘗試使用的感應來使用證明，但是在這個過程中被卡住了。我是否可以將此語句重新編寫爲n^2logn < = n^2？

是否有可能使用歸納來反證某些事物？例如，反駁n！= O（n^n）。或者僅僅通過顯示任意值可以說大於2不滿足該陳述來反駁該陳述是否有效？

我會在幾個小時內回覆您。

最後，爲了清楚起見，bigTheta聲明方程在增長正確時是等價的？

這意味着它們只相差一個常數。換句話說，如果將它乘以一個常量，它將總是低於它所限制的函數，並且如果將它乘以另一個常數，它將總是高於它所界定的函數。

編輯：

爲了測試大O，你看那個數學表示算法的增長作用小於或等於乘以大O功能的常數。

大歐米加顯示該算法大於或等於大歐米茄功能。

大西塔可以通過兩種方式得到證明：

1. 證明既大O和大歐米茄。

2. 假設算法是f（n）並且大的Theta函數是g（n）。爲了證明大的theta，你必須證明當n接近無窮大時，f（n）/ g（n）的極限是某個常數，即它不是0也不是無窮大。

我希望有幫助。如果您有更多問題，請告訴我，我很樂意爲您提供幫助。