[理工] [演算法] 複雜度計算問題
第一題
T(n) = n^4/4*T(n/2)+n^2
T(1)=1，求出asymptotic solution (in Θ)
第二題
Let f(n) and g(n) be positive functions satisfying
f(n) = g(n) for all n 小於等於 1
f(n) =f(2n/3)+f(n/2)+g(n) for all n 大於 1
Prove or disprove the following statements ?
1. If g(n) =Θ(n^2)) then f(n) = O(g(n))
2. If g(n) =Ω(n^2)) then f(n) = O(g(n))
以上幾題拜託各位了~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.24.168.207
※ 編輯: cksh3300110 來自: 114.24.168.207 (09/28 20:05)
※ 編輯: cksh3300110 來自: 114.24.168.207 (09/28 20:28)