Page 31 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 31
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-21
ตารางท ี่ 2.2 รูปแ บบฟงั กช์ นั ต า่ งๆ ที่เรียงล �ำ ดบั ต ามอัตราการเติบโต
ฟังก์ชนั ชอ่ื รปู แบบฟังกช์ ัน บ๊ิกโอ
c ฟังก์ชันค่าคงตัว (constant) O(1)
ฟังก์ชันลอการิธึม (logarithm)
log x ฟังก์ชันล็อกสแควร์ (log-squared) O(log x)
log2 x ฟังก์ชันเชิงเส้น (linear) O(log2 x)
-
x ฟังก์ชันกำ�ลังสอง (quadratic) O(x)
ฟังก์ชันกำ�ลังสาม (cubic)
x log x ฟังก์ชันเอ็กซ์โพเนนเชียล (exponential) O(x log x)
x2 O(x2)
x3 O(x3)
2x หรือ ex O(2x) หรือ O(ex)
ตวั อย่างท ่ี 2.14 จงเรียงล �ำดับอัตราการเติบโตของฟ ังก์ชันต ่อไปน้ีจากช ้าไปเร็ว
3x4 + 5 x2 4x6 6x log x 52 3x
วธิ ีท�ำ
ประมาณเป็นบ๊ิกโอจ ะได้ว ่า
3x4 + 5 = O(x4)
x2 = O(x2)
4x6 = O(x6)
6x log x = O(x log x)
52 = O(1)
3x = O(3x)
ดังน ้ัน เรียงล �ำดับอัตราการเติบโตของฟ ังก์ชันจากช ้าไปเร็วได้ด ังน้ี4x6 3x
52 6x log x x2 3x4 + 5
เม่ือพิจารณาถึงฟังก์ชันเวลา T(n) ที่ใช้ในการประมวลผลเพื่อแก้ปัญหาขนาด n ในการวัดประสิทธิภาพของ
ข้ันตอนวิธี ว่าท�ำงานช้าหรือเร็ว ฟังก์ชัน T(n) ถ้าโตข้ึนอย่างรวดเร็วเม่ือ n มีขนาดใหญ่ข้ึน แสดงว่าใช้เวลามากในการ
ประมวลผลข้อมูลขนาดใหญ่ นั่นคือ ท�ำงานได้ช ้าไม่มีประสิทธิภาพ ส่วนฟังก์ชัน T(n) ถ้าโตช ้า แสดงว่าใช้เวลาน้อยใน
การประมวลผลข้อมูลขนาดใหญ่ น่ันคือ ท�ำงานได้เร็วและมีประสิทธิภาพน่ันเอง จะเห็นได้ว่า การเติบโตของฟังก์ชัน
ในตารางท่ี 2.2 สรุปได้ว่า ถ้าขั้นตอนวิธีใช้ T(n) เป็นฟังก์ชันค่าคงตัว การท�ำงานของขั้นตอนวิธีจะไม่ขึ้นอยู่กับขนาด
ของข้อมูลเลย ถ้าขั้นต อนวิธีมีการใช้เวลา T(n) เป็นฟังก์ชันลอการ ิธึม การท�ำงานของข้ันต อนวิธีจะม ีประสิทธิภาพดีก ว่า
ขั้นตอนวิธีที่ใช้เวลาเป็นฟังก์ชันเชิงเส้น ในท่ีน่ีเม่ือพูดถึงฟังก์ชัน T(n) ให้นึกถึงฟ ังก์ชันใดๆ ที่มีโดเมนเป็นจ�ำนวนเต็ม
แทนได้ เช่น f(n) เป็นต้น
