[理工] [DS]Asymptotic Notation

[jim055006 (好崩潰)]

(1)        2           n       8
   Prove  n  + nlgn + --- = O(n )
                       2


   我是想存在c=1, n0=2, s.t. n>=n0,  2           n       8
                                    n  + nlgn + --- <= cn
                                                 2

   因為我的答案跟解答有所出入所以想問一下我這樣對不對....

(2)
   http://ppt.cc/GnT1

   此題我完全不知道再問啥??也不知道要怎麼做...似乎跟比大小無關

(3)k=0
   for(i=0;i<N;i++)
       for(j=0;j<i*i;j++)            求Big-Oh
           if(j%i==0)
              for(z=0;z<j;z++)
                  k++

                      3
   我算出來的答案是O(n ) 不知道對不對?



以上
有請大心高手解答
鋼溫!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.137.254.243
推 Byzantin:1.應該對 2.只要是O(n^k)都是 3.O(n^4)
請問B大 2.要求O(n^k)的話 那log的要怎麼看勒??
        3.為什麼是O(n^4)??我算一次都覺得z迴圈只做i次ㄝ??
※ 編輯: jim055006       來自: 223.138.226.199      (12/07 20:51)
→ Byzantin:O(n^k)不一定是tight asymptotic bound,例nlogn = O(n^2)
→ Byzantin:j=0*i , 1*i , ... , (i-1)*i時會執行第三層
→ Byzantin:0*i + 1*i + ... + (i-1)i = (i^3-i^2)/2 , i = 0 ~ N-1
→ jim055006:第二題我懂了感謝....第三題我在好好算算看