資料結構 › Ch1 演算法基礎
第 32 題/共 57 題 #DS-01-032 中 Asymptotic Notation 📝 ☆
Let f ( n ) f(n) f ( n ) and g ( n ) g(n) g ( n ) be asymptotically positive functions, where log ( g ( n ) ) ≥ 1 \log(g(n))\ge 1 log ( g ( n )) ≥ 1 and log ( f ( n ) ) ≥ 1 \log(f(n))\ge 1 log ( f ( n )) ≥ 1 for all sufficiently large n. Which of the following statement(s) is(are) correct?
A (A) f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) implies log ( f ( n ) ) = O ( log ( g ( n ) ) ) \log(f(n))=O(\log(g(n))) log ( f ( n )) = O ( log ( g ( n ))) B (B) log ( f ( n ) ) = O ( log ( g ( n ) ) ) \log(f(n))=O(\log(g(n))) log ( f ( n )) = O ( log ( g ( n ))) implies f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) C (C) f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) implies 2 f ( n ) = O ( 2 g ( n ) ) 2^{f(n)}=O(2^{g(n)}) 2 f ( n ) = O ( 2 g ( n ) ) D (D) ⌈ log n ⌉ ! = O ( n ) \lceil\log n\rceil ! = O(n) ⌈ log n ⌉! = O ( n ) E (E) 2 2 log n = O ( n ) 2^{\sqrt{2\log n}}=O(n) 2 2 l o g n = O ( n ) 📝 寫筆記
📄 交大110
▤ 完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎
‹ 本章題號 · 21–40 / 57 ›
難度 全部 57 易 24 中 26 難 7
學校 全部 57 台大 18 交大 16 成大 10 中央 11