Re: [理工] 資結時間複雜度比大小

看板Grad-ProbAsk作者Reylod (Reylod)時間13年前 (2012/06/29 20:28)推噓3(3推 0噓 2→)

留言5則, 2人參與討論串3/3 (看更多)

※ 引述《yyyyu (mm)》之銘言： : 一直被 lgn & logn 的混合打敗 @@ : 請問各位高手 , 這題複雜度大小如何比較? : 謝謝~ : 2 lgnlglgn lgn lglgn : lognlogn , n logn , 2 , 3 , n2 : 答案為 : : 2 lglgn lgn lgnlglgn : lognlogn < n logn < n2 < 3 < 2 2^(lgnlglgn) = 2^((lglgn)^lgn) = (lgn)^lgn n2^(lglgn) = nlgn 1. logn < n, logn ~= lgn => (logn)^2 < nlgn 2. nlgn < n^2logn 3. n^2logn < 3^(lgn) 4. 3^(lgn) < (lgn)^lgn (logn)^2 < nlgn < n^2logn < 3^(lgn) < (lgn)^lgn -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.176.209

推

jas1123kimo

07/03 09:49, , 1^F

07/03 09:49, 1^F

推

jas1123kimo

07/03 09:56, , 2^F

07/03 09:56, 2^F

→

Reylod

07/03 13:15, , 3^F

07/03 13:15, 3^F