[理工] [algo]-求解複雜度

[assassin88 (2010)]

一、      1.1                  1.1
  f(n) = n        g(n) = n(logn)

  我是取 log(f(n)) = 1.1logn
                                1.1
         log(g(n)) = log{ n(logn)  } = logn + 1.1loglogn
  f(n) = Θ(g(n))，這樣有算錯嗎？
  因為題目是用 lim 求的，求出來為0，是 f(n) = Ω(g(n))，麻煩指導一下。

二、f(n) = n + n/2 + n/4 + ... + 1 = n(logn)
    g(n) = n + 2n/2 + 3n/4 + ... + (lnn) = ？

    不知道f(n)有沒有求錯，請問 f(n) = ？(g(n))~~~感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.57.104.12
推 FRAXIS:第一題取log來判斷複雜度的地方有問題..
→ FRAXIS:第二題f是O(n), g我看不出來你要表達的級數是什麼..
→ assassin88:請問第一題是..？
→ assassin88:g是因為我求不出來= = 噢f(n)算錯..
推 polomoss:第一題f(n)=Omega(g(n))
→ assassin88:請問第一題的g(n)是等於 logn+1.1logn嗎？
→ assassin88:這樣不是Θ？
→ polomoss:不能這樣看，你把兩邊的n^1去掉，再取log就知道為何了
→ polomoss:左邊剩下n^0.1右邊為logn^k取log完左邊大
→ assassin88:原來如此~我懂了Orz..