418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 2

ข้อย่อย 1

ข้อความนี้ไม่เป็นจริง โดยการการแสดงตัวอย่างขัดแย้งคือ ให้ $f(n)=n^{2},g(n)=n^{3}$

จะได้ว่า $f(n)=O(g(n))$ นั่นคือ $n^{2}=O(n^{3})$ เป็นจริง แต่ จะได้ว่า $g(n)=O(f(n))$ นั่นคือ $n^{3}=O(n^{2})$ ไม่เป็นจริง

ข้อย่อย 2

ข้อความนี้ไม่เป็นจริง จะแสดงตัวอย่างขัดแย้ง คือให้ $f(n)=n,g(n)=n^{2}$

จะได้ว่า $f(n)+g(n)$ คือ $n+n^{2}=O(n^{2})$

ข้อย่อย 4

ข้อความนี้ไม่เป็นจริง จะแสดงตัวอย่างขัดแย้งคือให้ $f(n)=1/n$ จะได้ว่า ${(f(n))}^{2}=1/n^{2}$

ซึ่ง $(1/n)\neq O(1/n^{2})$

ข้อย่อย 5

ข้อความนี้เป็นจริง จะทำการพิสูจน์

จากที่รู้ว่า $f(n)=O(g(n))$ เป็นจริง นั่นคือ สำหรับจำนวนเต็มบวก $c_{1},n_{0}^{'}$ บางตัว แล้ว $0\leq f(n)\leq (c_{1}(g(n))$ จะเป็นจริง สำหรับทุก ๆ $n>n_{0}^{'}$

ต้องการแสดงว่า $g(n)=\Omega (f(n))$ นั่นคือต้องการจำนวนเต็มบวก {"type":"https://mediawiki.org/wiki/HyperSwitch/errors/bad_request","title":"Bad Request","method":"POST","detail":["TeX parse error: Prime causes double exponent: use braces to clarify"],"uri":"/complete"}$c_{2},n_{0}^{'}'$ บางตัว ที่ทำให้ $0\leq (c_{2}(f(n))\leq g(n)$ จะเป็นจริง สำหรับทุก ๆ {"type":"https://mediawiki.org/wiki/HyperSwitch/errors/bad_request","title":"Bad Request","method":"POST","detail":["TeX parse error: Prime causes double exponent: use braces to clarify"],"uri":"/complete"}$n>n_{0}^{'}'$

จากข้างต้นจะให้ {"type":"https://mediawiki.org/wiki/HyperSwitch/errors/bad_request","title":"Bad Request","method":"POST","detail":["TeX parse error: Prime causes double exponent: use braces to clarify"],"uri":"/complete"}$c_{2}=1/c_{1},n_{0}^{'}'=n_{0}^{'}$ ก็จะได้ว่า $g(n)=\Omega (f(n))$ เป็นจริง