[理工] 資料結構_關於複雜度比大小題型

看板Grad-ProbAsk作者 (fmtshk)時間6年前 (2019/05/26 21:33), 編輯推噓0(0推 0噓 5→)
留言5則, 2人參與, 6年前最新討論串1/1
https://i.imgur.com/lk97j3i.jpg
想請問上面這4個如何判斷大小呢? [√2^log(n)]書上有寫如何化簡成[√n] 但化簡完後還是看不出誰大 原本以為[n^√2/logn]比[√n]大 (有指數?) 結果解答是後者較大 附上內容https://i.imgur.com/tF0VFls.jpg
這種題目我寫不出來時，都會隨便找數字代進去做比較 但也無法帶很大的數字，所以好像沒甚麼用? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.132.163 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1558877623.A.85C.html
→
05/26 21:53, 6年前 , 1F
有錯麻煩指正 原則：1<log<n^c 其中0<c<1，這樣來看第一個，
05/26 21:53, 1F
→
05/26 21:53, 6年前 , 2F
左右兩邊單看logn一樣大沒問題，差別在於log跟√，由原則可
05/26 21:53, 2F
→
05/26 21:53, 6年前 , 3F
知√那邊較大，所以第一行是大於，第二行可看成√(2/logn)與
05/26 21:53, 3F
→
05/26 21:53, 6年前 , 4F
logn/2，顯然後者較大，所以是小於
05/26 21:53, 4F
→
05/27 07:54, 6年前 , 5F
懂了 感謝~
05/27 07:54, 5F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1SwfMtXS (Grad-ProbAsk)