推 suhorng:4,5不對 2^n, 4^n成長比n!慢 03/08 22:11
已更正 感謝 看成 double exponential time了 囧"
※ 編輯: seiki 來自: 114.47.211.34 (03/08 22:20)
→ kevinying:謝謝, 我會找時間把表背一下!! 03/09 00:40
※ 引述《kevinying (police_is_dog)》之銘言：
: determine whether the following statement are correct
T (1) n^2 + n^3logn = Ω(n^3)
n^2 + n^3logn = Θ(n^3logn) = Ω(n^3)
F (2) n^n = O(n!)
n! = O(n^n)
T (3) 2010n^2 - 2n + 1 = Θ(n^2)
T (4) 4^n = O(n!)
T (5) 2^n = O(n!)
n! > 4^n > 2^n
T (6) n^2 + nlogn = O(n^30)
n^2 + nlogn = O(n^2) = O(n^30)
附上WIKI的Table of common time complexities
http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities
基本上把握這個表 和 函數相加複雜取決於較大者的原則就行了
: 這幾題小弟不太會解,或解了不太確定對不對,麻煩各位大大幫忙解答..謝謝!!
: 請在請問一下遞迴的費氏數列的空間複雜度,
: 老師有教過空間複雜度求法但好像沒提過空間的, 謝謝!
看是哪種寫法
recursion 版 : space complexity is O(n)
iteration 版 : space complexity is O(1)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.47.211.34