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

作者: fmtshk (fmtshk)   2019-05-26 21:33:41
https://i.imgur.com/lk97j3i.jpg
想請問上面這4個如何判斷大小呢?
[√2^log(n)]書上有寫如何化簡成[√n]
但化簡完後還是看不出誰大
原本以為[n^√2/logn]比[√n]大 (有指數?)
結果解答是後者較大
附上內容https://i.imgur.com/tF0VFls.jpg
這種題目我寫不出來時,都會隨便找數字代進去做比較
但也無法帶很大的數字,所以好像沒甚麼用?
作者: DLHZ ( )   2019-05-26 21:53:00
有錯麻煩指正 原則:1<log<n^c 其中0<c<1,這樣來看第一個,左右兩邊單看logn一樣大沒問題,差別在於log跟√,由原則可知√那邊較大,所以第一行是大於,第二行可看成√(2/logn)與logn/2,顯然後者較大,所以是小於
作者: fmtshk (fmtshk)   2019-05-27 07:54:00
懂了 感謝~

Links booklink

Contact Us: admin [ a t ] ucptt.com