作者fmtshk (fmtshk)
看板Grad-ProbAsk
標題[理工] 資料結構_關於複雜度比大小題型
時間Sun May 26 21:33:41 2019
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
→ DLHZ: 有錯麻煩指正 原則:1<log<n^c 其中0<c<1,這樣來看第一個, 05/26 21:53
→ DLHZ: 左右兩邊單看logn一樣大沒問題,差別在於log跟√,由原則可 05/26 21:53
→ DLHZ: 知√那邊較大,所以第一行是大於,第二行可看成√(2/logn)與 05/26 21:53
→ DLHZ: logn/2,顯然後者較大,所以是小於 05/26 21:53
→ fmtshk: 懂了 感謝~ 05/27 07:54