Re: [離散]一題證明題

[doom8199 (～口卡口卡 修～)]

※ 引述《waxxxbang (機八毛)》之銘言：
: Suppose f = Ω(1) (at least order 1), a, b, are both constant, and b > 0.
: prove that (logb |f|)^a = O(f).
:                ↑
:                 b是下標
: 拜託各位了 > <

---

    由  f = Ω(1)  可知道

    存在 ε>0  and N>0   , 使得對所有的 n≧N  , 皆滿足  ε≦ f(n)


    令  z = log_b |f|  →  f = b^z

    不難證明存在 ε2>0  and N2>0

    使得對所有的 z≧N2 , 皆滿足   z^a ≦ ε2*b^z

   →  z^a =  O(b^z)    (多項式函數可被指數函數 bounded)

   or  (log_b |f|)^a = O(f(n))


---

   要證明  z^a =  O(b^z)  是對的

   可以用反證法:

   假設 對所有的 ε2≧ε0  for some ε0>0 and N2>0

        皆存在  z≧N2  , 使得  z^a ＞ε2*b^z

     →  z^a ＞ε2*b^z ≧  ε2*b^(N2)

                b^[(N2)/a]
     →  ε2 ＜ __________      ______(1)
                    a

                                  b^[(N2)/a]
   此時若選擇   ε2 = max{ ε0 ,  __________ }     (滿足原假設)
                                      a
   會與 (1)式 產生矛盾



   即原命題 z^a =  O(b^z)  成立



    ps:  你也可以用直接証法 or　數學歸納法

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.151
※ 編輯: doom8199        來自: 140.113.141.151      (11/03 19:42)
推 waxxxbang   :雖然有點不懂 但是謝謝囉^^
→ musicbox810 :怎麼知道b^z > b^N2   b又沒大於還是小於1
→ doom8199    :對齁，忘記考慮了，感謝樓上提醒
→ doom8199    :不過只要用換底公式讓它變成  (log_c b)^a
→ doom8199    :丟到分母就可以了。不過這樣講起來，a一定要是正整數
→ doom8199    :不然  (負值)^(小數)  這個值會出問題