推 moonlights:專業好文必推 04/17 20:30
推 nash3629:你今天世紀了嗎 04/17 21:08
推 WAYS22275: 專業地下助教 04/17 21:38
推 einstein1217:PK!!PK!! 04/17 21:49
考古題兩年都出的題目
‧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