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

P. 35

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

ตอนที่ 2.2
การว ิเคราะหข์ ัน้ ตอนวิธี

โปรดอ ่านห ัวเร่ือง แนวคิด และวัตถุประสงค์ข องตอนท ่ี 2.2 แล้วจ ึงศึกษารายละเอียดต ่อไป

หวั เร่อื ง

2.2.1 การว ิเคราะห์ประสิทธิภาพข องข ้ันต อนว ิธี
2.2.2 การเปรียบเทียบประสิทธิภาพข องข ้ันต อนวิธี

แนวคิด

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

2. ก ารเปรียบเทียบประสิทธิภาพของขั้นตอนวิธีต่างๆ ที่สามารถแก้ปัญหาเดียวกันได้ อาศัยการ
พิจารณาและเปรียบเทียบบิ๊กโอของแต่ละขั้นตอนวิธีเพ่ือการเปรียบเทียบการเติบโตของฟังก์ชัน
เวลา ท�ำให้ทราบว่าขั้นตอนวิธีไหนท�ำงานได้มีประสิทธิภาพดีกว่าในแง่ของความเร็วเมื่อข้อมูล
ม ีข นาดใหญ่

วัตถปุ ระสงค์

เม่ือศ ึกษาตอนที่ 2.2 จบแ ล้ว นักศึกษาสามารถ
1. ประมาณฟ ังก์ชันเวลา T(n) ของข้ันต อนว ิธีท่ีก�ำหนดให้ได้
2. ประมาณป ระสิทธิภาพของขั้นต อนว ิธีท ่ีก �ำหนดให้ในร ูป บิ๊กโอได้
3. เปรียบเทียบป ระสิทธิภาพของข ั้นตอนวิธีต ่างๆ ได้

30 31 32 33 34 35 36 37 38 39 40