下界歐米茄表示法

我必須證明某些數字S大於Ω（| V |），其中| V |是頂點的數量。我讀到了漸近符號的定義，但我仍然對這些例子感到困惑。在我的例子中，我證明* S≥1 + 1/2 + 1/3 + .... + 1/| V |。我完成了嗎？有人可以給我類似的例子Ω的功能？下界歐米茄表示法

來源

2014-09-02 sammy333

這可能更好地屬於[程序員stackexchange]（http://programmers.stackexchange.com/）。另外，請不要忘記關於SO的問題政策（http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions）。 – 2014-09-02 19:36:06

求和

1/1 + 1/2 1/3 + ... + 1/n的

給出第n個harmonic number，表示ħ_Ñ。一個非常有用的事實是H（n）= Θ（log n），更具體地說是H（n）≥ ln n-1。因此，如果你已經證明S = H _{| V |因爲| V | = 0，所以S = ，你已經證明S = Θ（| V | lg | V |），因此S = Ω（| V | lg | V |增長速度至少與| V |一樣快。}

希望這有助於！

來源

2014-09-02 20:04:04 templatetypedef

非常感謝！我可以問另一個問題嗎？大約1/2 + 1/2 + ... + 1/2（V次）。這也等於Ω（| V |），對嗎？ – sammy333 2014-09-02 20:08:19

那麼，1/2 + 1/2 + ... + 1/2 | V |次是| V |/2，這是歐米茄（| V |）:-) – templatetypedef 2014-09-02 20:17:02

下界歐米茄表示法

回答

相關問題