Re: [商管] DS資結時間空間複雜度問題
※ 引述《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
推
03/08 22:11, , 1F
03/08 22:11, 1F
已更正 感謝 看成 double exponential time了 囧"
※ 編輯: seiki 來自: 114.47.211.34 (03/08 22:20)
→
03/09 00:40, , 2F
03/09 00:40, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：