推 jimmyoic :complexity!!? 03/29 17:34
推 suhorng :他的證法是對的~ 但是極限比純粹上下界更嚴格 03/29 20:34
這是我上禮拜的一個作業某題題目
已經交出去了
不過還是想不太懂
題目大概是問
lg(n!) is O or Ω or θ of lg(n^n)?
(lg表以二為底的log)
我已經用O-notation的定義找出lg(n!) = O(lg(n^n))
我是直接把lg乘的轉成加的去比較
但是在判斷Ω求下界時遇到了問題
我去請教了一位說會寫的同學
他是用類似取極限的方式
Ω原本定義中下界的不等式是
0 <= c*g(n) <= f(n) (不曉得怎怎麼直接打小於等於的符號)
將f(n)移向變成
0 <= c*g(n)/f(n) <= 1
然後取極限n趨近於無窮大
用 L'Hospital(羅必達?)去算出來
概念好像是這樣
不過他是直接lg(n!)和lg(n^n)兩個相除取極限
根據他算的結論
lg(n!) = Ω(lg(n^n))
再綜合兩O和Ω兩者得θ
但是我覺得這裡有點怪怪的
況且這只是算出n趨近於無窮大會成立
好像和存在有個n0的大於n會成立並不是若且唯若的關係
後者可以推至前者
但反向感覺不一定成立
這樣證好像不太完全
不過我自己也沒有辦法證明到底lg(n^n)是不是lg(n!)的下界
不知板上是否有人能為我解惑呢?
或是有甚麼比較好的方法?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.117.211.109
※ 編輯: lovepy 來自: 140.117.211.109 (03/29 14:22)
※ 編輯: lovepy 來自: 140.117.211.109 (03/29 14:26)