Page 16 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 16
2-6 โครงสร้างข้อมูลและขั้นตอนวิธี
0e + 00 1e+06 2e + 06 3e + 06 4e + 06 g(x) = x2
f(x)
f(x) = 1000x
0 500 1000 1500 2000
X0
ภาพท ี่ 2.1 ความส มั พันธร์ ะหว่างค่า x0 กบั ค า่ ของฟ ังกช์ ัน 1000x และ x2
1. บก๊ิ โอ
จากตัวอย่างความสัมพันธ์ของฟังก์ชัน f(x) และ g(x) ข้างต้น เน่ืองจาก g(x) มีอัตราการเติบโตของฟังก์ชัน
ที่เร็วกว่า f(x) อาจกล่าวได้ว่า g(x) เป็นขอบเขตบนของ f(x) และสามารถเขียนแทนสัญลักษณ์บ๊ิกโอ (big O) ได้ดังนี้
f(x) = O(g(x)) โดยสัญลักษณ์บิ๊กโอจะใช้อธิบายขอบเขตบนของการเติบโตของฟังก์ชัน นั่นหมายความว่า f(x) จะมี
อัตราก ารเติบโตไม่เกิน g(x) และในท างค ณิตศาสตร์ส ามารถเขียนเป็นบทนิยามได้ด ังน้ี
บทนิยาม 2.1 บกิ๊ โอ (O)
ฟังก์ชัน f(x) สามารถป ระมาณข อบเขตบ นได้ด้วยบ ิ๊กโอข อง g(x) เขียนแ ทนด้วย
f(x) = O(g(x)) ถ้าม ีค่าคงตัวบวก c ≥ 0 และ x0 ≥ 0 ที่ท ำ�ให้ |f(x)| ≤ c|g(x)| เมื่อ x ≥ x0
หมายเหต:ุ โดยส่วนใหญ่จะพิจารณาฟังก์ชันที่มีค่าเป็นบวก ทำ�ให้ละเว้นการพิจารณาค่าสัมบูรณ์ได้ และทำ�ให้การวิเคราะห์
ง่ายขึ้น โดยเฉพาะอ ย่างย ิ่งการพ ิจารณาฟังก์ชันเวลา T(n) ซึ่งป กติมีค่าม ากกว่าหรือเท่ากับศ ูนย์
จากบทนิยาม 2.1 บิ๊กโอ จะได้ว่า ถ้าสมมติให้ f และ g เป็นฟังก์ชันใดๆ กล่าวได้ว่า f(x) = O(g(x)) เมื่อมีค่า
คงตัว c และ x0 ท่ีท�ำให้ |f(x)| ≤ c|g(x)| เม่ือ x ≥ x0 (เรียกว่า f(x) เป็นบ๊ิกโอของ g(x)) จะเห็นว่า ค่าคงตัว c และ x0
ในบทนิยามของบ๊ิกโอคือตัวยืนยันความสัมพันธ์ f(x) = O(g(x)) ดังนั้น เพื่อที่จะแสดงว่า f(x) = O(g(x)) ต้องหา
ตัวยืนย ันเพียงหน่ึงคู่เพ่ือแ สดงค วามสัมพันธ์น้ี
การเปรียบเทียบอัตราก ารเติบโตข องฟ ังก์ชันสองฟังก์ชัน บทนิย ามบ ๊ิกโอน้ีบอกได้ว่าอ ัตราก ารเติบโตข อง f(x)
น้อยกวา่ หรือเท่ากับอัตราการเติบโตของ g(x) หรือเรียกอีกอย่างหนึ่งว่าอัตราการเติบโตของ g(x) เป็นขอบเขตบน
(upper bound) ของอ ัตราการเติบโตของ f(x)
จากตัวอย่างการเปรียบเทียบฟังก์ชัน f(x) = 1000x และ g(x) = x2 ข้างต้น และบทนิยามบิ๊กโอน้ี สรุปได้ว่า
จะมีจุด x0 ท่ีท�ำให้ cg(x) มีค่าเท่ากับ f(x) นั่นคือ ในที่นี้จาก f(x) = 1000x และ g(x) = x2 ซ่ึงกราฟทั้งสองจะตัดกันที่
x = 1000 (ดังแ สดงในภ าพที่ 2.1)
