考古題兩年都出的題目 ‧Rank the following function blablabla 基本上 n! > c^n > n^c > nlgn = log(n!) > n > lgn > lglgn > lg*n > c 上面是用想的推出來的 不過他會考一些次常用的 例如說 (lgn)! 會不知道排哪 所以要稍微背一下 課本作業解答 2^2^(n+1) > 2^2^n > (n+1)! > n! > e^n > n2^n > 2^n > (3/2)^n > (lgn)^(lgn) = n^lglgn > (lgn)! > n^3 > n^2 = 4^lgn > nlgn ~ lg(n!) > n = 2^lgn > (√2)^lgn = √n > (lgn)^2 > lgn > √lgn > lnlnn > 2^(lg*n) > lg*n ~ lg*lgn > lglg*n > n^(1/lgn) = 2 ~ 1 說明： f > g ： f 是 g 的 upper bound f = g ： f 和 g 化簡過後是同一個方程式 f ~ g ： f 是 g 的 tight bound 附上中意版口訣 演算法 函數比大小口訣 e^n > 2^n > lg(n)^lg(n) > lg(n!) > n^2 伊恩餓恩伊恩餓恩 肉個恩 肉個恩 肉個階恩平方 肉個恩階恩平方 > nlg(n) > n = 2^lg(n) > (lg(n))^2 > lg(n) 恩肉個恩 恩肉個恩 火星文翻譯 兩隻老虎兩隻老虎 跑得快 跑得快 一隻沒有眼睛 一隻沒有耳朵 真奇怪 真奇怪 BY中意 all rightreserved --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.68.15.209