考古题两年都出的题目 ‧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