[問題] 計算時間複雜度
想請問三題關於時間複雜度的計算
第一題 證明 http://0rz.tw/tPSN9
我知道指數成長會比lgn快 但是考試出來應該不能只寫這句吧
不知道有沒有比較嚴謹的證法
第二題 求upper and lower bound as tigth as possible
http://0rz.tw/TLpdn
第一行是題目 第二行是小弟的想法 將每個平方項展開後
算出的答案是系塔(n^3) 不知道對不對
第三題 求upper and lower bound as tigth as possible
http://0rz.tw/Hp8ny
第一行是題目 第二行是小弟的想法 最後算出是 1/lgnlgn
但始終感覺怪怪的 1/lgnlgn 跑的速度不是會非常快嗎
不知有沒有算錯
順便問一下第二和第三題 一直遞迴展開的最後一項是要寫0好還是1好
謝謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.1.74
※ 編輯: lf963 來自: 111.255.1.74 (11/07 22:57)
討論串 (同標題文章)