幫助大歐米茄證明？

我無法解決證明。其中，t（n）爲< = cn^1.6，c爲常數。一般來說，大歐米茄是大O的反面，因爲它是最好的情景並尋找下界。所以存在c和n0使得n> = n0。但我不確定如何將此應用於證明以及如何操作方程中的常數來找出c和n0並證明t（n）是Omega（n^1.6）。幫助大歐米茄證明？

T（N）=（N-3logn）^ 1.6 + 5N^1.5 + 7是歐米茄（N^1.6）

任何人都可以提供關於如何執行此類型的問題的一些見解？提前致謝！

另外，我沒有得到任何批評，因爲從我下面的評論中收到，這不是一個家庭作業問題，而是從一組練習中採取的一個例子，以便更容易讓某人解釋這種類型背後的一般概念的問題。 BIG-歐米茄

來源

2011-02-24 deedex11

你基本上需要證明（而且這很不重要），與n^1.6相比，omega-wise log^1.6 n和n^1.5是」微不足道的「。 – chx 2011-02-24 22:48:44

定義：F（N）=歐米茄（G（N））當且僅當常數C和K存在，使得對所有的n> K，F（N）> C * G（N）

換句話說，你需要能夠這樣說：「我選擇C = 5，現在所有n> 1000，f（n）> 5 * g（n），所以在那裏。」

現在我們來看看你的問題。

t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 is Omega(n^1.6) 

C * n^1.6 < (n-3logn)^1.6 + 5n^1.5 + 7

除n^1.6

C < ((n-3logn)/n)^1.6 + 5n^-0.1 + 7/n^1.6 
C < (1 - 3logn/n)^1.6 + 5n^-0.1 + 7/n^1.6

那麼讓我們來看看這三個方面逐一（更正式的證明將需要的，當然，但這些都是簡單的）。

1. (1 - 3logn/n)^1.6 = (1 - 0.smth)^1.6 = (0.smth)^1.6 < 1 for n > 2 
2. 5n^-0.1 = 5/n^0.1 = 5/smth greater than 1 < 5 for n > 2 
3. 7/n^1.6 = 7/smth large < 1 for n > 2

所以我們看到，對任意n> 2，C < 1 + 5 + 1 = 7

現在，你可以說：「我選擇C = 7，對於任意n> 2，C * n^1.6 < ...「

來源

2011-02-25 10:18:02 iluxa

謝謝！我現在明白了！ – deedex11 2011-02-25 16:19:21

幫助大歐米茄證明？

回答

相關問題