Page 15 - โครงสร้างข้อมูลและขั้นตอนวิธี

การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-5

เร่ืองท​ ่ี 2.1.1
ความห​ มายข​ อ​งบิ๊กโ​อ บ๊ิกโ​อเ​มก​ า และ​บกิ๊ ​ที​ตา

ใน​เร่ือง​นี้​จะ​กล่าว​ถึง​การ​เติบโต​ของ​ฟังก์ชัน การ​ศึกษา​อัตรา​การ​เติบโต​ของ​ฟังก์ชัน​เป็น​เร่ือง​ท่ี​น่า​สนใจ​และ​
เกยี่ วขอ้ ง​โดยตรง​กบั ​การ​วดั ​ประสทิ ธภิ าพ​ของ​ขนั้ ​ตอน​วธิ ​ดี ว้ ย​การ​ค�ำนวณ​หา​ฟงั กช์ นั ​เวลา โดย​สมมต​ิให้ T(n) เปน็ ​ฟงั กช์ นั ​
เวลา​ท่ี​ใช้​ใน​การ​ประมวล​ผล​เพ่ือ​แก้​ปัญหา​ขนาด n ของ​ข้ัน​ตอน​วิธี​หนึ่ง ดัง​นั้น ​อัตรา​การ​เติบโต​ของ​ฟังก์ชัน T(n) จึง​ใช​้
เป็น​ตัว​วัด​ประสิทธิภาพ​ของ​ข้ัน​ตอน​วิธี​นี้​ได้ โดย​การ​พิจารณา​ว่า ฟังก์ชัน T(n) เพ่ิม​ขึ้น​เร็ว​หรือ​ช้า​ใน​สัดส่วน​แบบ​ใด​กับ​
ขนาดข​ องป​ ัญหา ขั้นต​ อนว​ ิธีท​ ี่​มี​ประสิทธิภาพค​ ือ เวลาท​ ี่ใ​ช้ท​ �ำงาน T(n) เพิ่มข​ ้ึนช​ ้าเ​มื่อข​ นาดข​ องป​ ัญหา (n) เพิ่มข​ ้ึนน​ ่ันเอง
ดัง​น้ัน อัตราก​ าร​เติบโต​ของ​ฟังก์ชันจ​ ึง​ส�ำคัญ และ​ในเ​ร่ือง​นี้จ​ ะศ​ ึกษาส​ ัญลักษณ์ท​ ี่ใ​ช้​อธิบาย​การ​เติบโต​ของ​ฟังก์ชัน T(n)
เพ่ือ​น�ำไ​ป​ประยุกต์ใ​ช้อ​ ธิบายป​ ระสิทธิภาพ​ของข​ ั้นต​ อน​วิธี

ให้​พิจารณา​ฟังก์ชัน 2 ฟังก์ชัน​ใดๆ ท่ี​มี​ค่า​มากกว่า​ศูนย์ เช่น​ ฟังก์ชัน f(x) = 1000x และ​ฟังก์ชัน g(x) = x2
จะ​เห็น​ว่า ฟังก์ชัน f(x) จะ​มี​ค่า​มากกว่า g(x) เมื่อ x มี​ค่า​น้อย แต่​เมื่อ x มี​ค่า​มาก (มากกว่า 1000) แล้ว g(x) จะ​มี​ค่า​
มากกว่า f(x) ทั้งน้ี​ เนื่องจาก g(x) เป็นฟ​ ังก์ชันท​ ี่​มีก​ ารเ​ติบโตท​ ี่เ​ร็วก​ ว่า f(x) ดังแ​ สดงใ​นต​ ารางท​ ี่ 2.1 และภ​ าพท​ ี่ 2.1 สังเกต​
ได้ว​ ่า ที่ x = 1000 ซึ่ง​เป็นจ​ ุดต​ ัด​ระหว่างฟ​ ังก์ชัน f(x) และ g(x) เป็นจ​ ุด​เปลี่ยนค​ วามส​ ัมพันธ์ร​ ะหว่าง f(x) กับ g(x) นั่นเอง
ท�ำให้​ทราบ​ว่า​ เม่ือ x มี​ค่า​มากกว่า 1000 ฟังก์ชัน g(x) มี​ค่าม​ ากกว่า f(x) แสดงว​ ่า g(x) มี​อัตรา​การ​เติบโต​ของ​ฟังก์ชัน​ที​่
เร็ว​กว่า f(x) ซึ่งส​ ามารถอ​ ธิบาย​ได้ด​ ้วย​บทน​ ิยามต​ ่างๆ ดัง​ต่อไ​ปน​ ี้

ตาราง​ท่ี 2.1 คา่ ข​ อง​ฟังก์ชัน f(x) = 1000x และ g(x) = x2

x f(x) = 1000x g(x) = x2
1 1,000 1
10 10,000
100
100 100,000 10,000
1,000 1,000,000 1,000,000
10,000 10,000,000 100,000,000
100,000 100,000,000 10,000,000,000