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})$

ข้อย่อย 3

สมมติให้ $f(n)=O(g(n))\,$ แสดงว่ามีค่าคงที่ $c'>0\,$ และ $n'_{0}\,$ ที่ทำให้ถ้า $n\geq n'_{0}\,$ แล้ว $f(n)\leq c'g(n)\,$ ซึ่งหมายความว่า $2^{f(n)}\leq 2^{c'g(n)}={2^{c'}}^{2^{g(n)}}\,$ ด้วยเหตุนี้ $2^{f(n)}=O(2^{g(n)})$ ด้วยเนื่องจากเราสามารถเลือก $c=2^{c'}\,$ และ $n_{0}=n'_{0}\,$ ได้

ข้อย่อย 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_{1}$ บางตัว แล้ว $0\leq f(n)\leq (c_{1}(g(n))$ จะเป็นจริง สำหรับทุก ๆ $n>n_{1}$

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

จากข้างต้นจะให้ $c_{2}=1/c_{1},n_{2}=n_{1}$ ก็จะได้ว่า $g(n)=\Omega (f(n))$ เป็นจริง

ข้อย่อย 6

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

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