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 cg(n)\,$ ซึ่งหมายความว่า $2^{f(n)}<2^{cg(n)}=2^{c}\cdot 2^{g(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})$