Research Space for Linear Algebra & Discrete Mathematics
若只是要比較兩個函數的complexity誰大誰小, 可以不用微, 用看的就好了:(1) 算等比級數和, 得 f(n) = O(2^-n) = O(g(n))(2) 把f(n)和g(n)分別看成數列{a}和{b}的總和, 即 {a}=n, n/2, ..., 1; {b}=n, 2n/2, ..., ln(n)則 b_i = i(a_i) 顯然大於 a_i, for i = 1,...,ln(n) 所以 f(n) = O(g(n))
張貼留言
1 則留言:
若只是要比較兩個函數的complexity誰大誰小,
可以不用微, 用看的就好了:
(1) 算等比級數和, 得 f(n) = O(2^-n) = O(g(n))
(2) 把f(n)和g(n)分別看成數列{a}和{b}的總和,
即 {a}=n, n/2, ..., 1; {b}=n, 2n/2, ..., ln(n)
則 b_i = i(a_i) 顯然大於 a_i, for i = 1,...,ln(n)
所以 f(n) = O(g(n))
張貼留言