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)=2n\,$ เราได้ว่า $f(n)=O(n)\,$ แต่ $2^{f(n)}=2^{2n}=4^{n}\neq O(2^{n})\,$

ข้อย่อย 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})$