T(n)=sin n 的big O 是多少 ?

Question

T(n)=sin n 和 T(n)=1/1+n^2 的big O 是多少 ?
請寫出詳細過程...謝謝

對不起...我少個括弧..T(n)=1/(1+n^2)..這樣才對= =

Answer 1

第二題, 不管 n 為何, 要 1 個乘 (因為要 n 乘 n), 及 1 個加, 1 個 除,
共 3 個運算, 對於 n 是常數, 所以是 O(1).

第一題, sin n 通常是用其麥克洛林多項式 (Mclaurin polynomial) 求近似值,
即 n - (n^3)/3! + (n^5)/5! - (n^7)/7! + ... 一直加到某一項 (由內建函數決定),
花的運算或時間是由此多項式的項數決定, 也和 n 無關,
所以是 O(1).

2007-06-29 09:28:44 補充：
> T(n)=1/(1+n^2)..這樣才對= =

我知道. 答案及解釋不變.