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

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

การ​นับ​ตัว​ด�ำเนิน​การ​นี้​ท�ำให้​สามารถท​ ราบค​ ร่าวๆ ได้ว​ ่า​ข้ัน​ตอน​วิธี​น้ันจ​ ะท​ �ำงาน​มาก​น้อยห​รือใ​ช้​เวลาม​ าก​น้อย​ประมาณ​
เท่าใด​เป็นห​ น่วย​ของเ​วลา ให้พ​ ิจารณา​ตัวอย่าง​การ​นับต​ ัว​ด�ำเนิน​การด​ ังต​ ่อไ​ป​นี้ โดยค​ ิดว​ ่า​แต่ละ​ตัวด​ �ำเนิน​การใ​ช้เ​วลา​ไป
1 หน่วย​เวลา​เท่าๆ กัน โดย​หน่วย​เวลา​น้ี​อาจ​เป็น นาที วินาที ช่ัวโมง หรือ​เป็น​หน่วย​เวลา​ของ​ซีพียู​ก็ได้ ทั้งน้ีข้ึนอยู่กับ
การพ​ ิจารณา​ปัจจัย​ทางด​ ้าน​ฮาร์ดแวร์แ​ ละอ​ ่ืนๆ

ตัวอย่าง​การ​นับต​ ัวด​ �ำเนิน​การ เช่น 2 * 3 + 5 จะ​มี​ตัว​ด�ำเนินก​ าร​ท้ังหมด 2 ตัว คือ คูณ (*) กับ​บวก (+) ดังน​ ้ัน
นับ​ตัวด​ �ำเนินก​ ารท​ ั้งหมด​ได้ 2 ตัว เป็นต้น

ตวั อยา่ ง​ท่ี 2.16 จงน​ ับ​ตัวด​ �ำเนินก​ ารท​ ้ังหมดข​ อง (2 + 3) * 5 — (6 + 8)
วธิ ที​ �ำ

จะไ​ด้​ว่า​มี​ตัว​ด�ำเนิน​ทั้งหมด 4 ตัว คือ บวก 2 ตัว ลบ 1 ตัว และค​ ูณ 1 ตัว

ตวั อยา่ งท​ ่ี 2.17 จงน​ ับต​ ัวด​ �ำเนิน​การท​ ้ังหมด​ของ a = 4 * 5 + (2 / 3) * 6
วิธี​ท�ำ

จะไ​ด้ว​ ่า​มี​ตัวด​ �ำเนิน​ท้ังหมด 5 ตัว คือ บวก 1 ตัว คูณ 2 ตัว หาร 1 ตัว และ​ตัวด​ �ำเนินก​ าร​เท่ากับอ​ ีก 1 ตัว

ดังน​ ้ัน ส�ำหรับข​ ั้นต​ อนว​ ิธี​หนึ่งๆ พื้นฐ​ านก​ ารค​ ิดค​ ่าห​ น่วยเ​วลา สามารถ​พิจารณา​ได้ด​ ังนี้
1) การ​ให้ค​ ่า​ข้อมูล​กับต​ ัวแปร (assignment) คิดเ​ป็น 1 หน่วยเ​วลา
2) การต​ รวจ​สอบ​เง่ือนไข (condition) คิด​เป็น 1 หน่วยเ​วลา เช่น การ​ตรวจ​สอบ​เง่ือนไข​ใน if-else
3) การป​ ระมวลผ​ ลต​ ัว​ด�ำเนิน​การ (operation) คิด​เป็น 1 หน่วยเ​วลา เช่น 2 + 3
4) การ​ประมวล​ผล​แบบ​ท�ำซ​ �้ำ (loop) คิด​หน่วย​เวลา​ตาม​การ​ตรวจ​สอบ​เง่ือนไข​และ​จ�ำนวน​ครั้ง​ท่ี​วน​ท�ำซ​ ้ํา
ค�ำส​ ่ัง​ต่างๆ เช่น while loop และ for loop เป็นต้น
พิจารณาส​ ่วนข​ อง​รหัส​เทียม​ดัง​ต่อ​ไป​น้ี

1 a := 1
2 b := 2
3 sum := a + b
4 multiply := a * b
5 average := (a + b) / 2

จะ​ได้​ว่า
บรรทัด​ที่ 1 เป็นการใ​ห้ค​ ่า​ข้อมูล​กับ​ตัวแปร a คิด​เป็น 1 หน่วยเ​วลา
บรรทัดท​ ่ี 2 เป็นการใ​ห้ค​ ่า​ข้อมูลก​ ับ​ตัวแปร b คิดเ​ป็น 1 หนว่ ย​เวลา
บรรทัดท​ ี่ 3 ประกอบ​ด้วย การ​ประมวล​ผล​การ​บวก​คิดเ​ป็น 1 หน่วย​เวลา และก​ ารใ​ห้​ผล​บวก​ท่ีไ​ด้​กับ​ตัวแปร
sum คิด​เป็นอ​ ีก 1 หน่วยเ​วลา ดัง​น้ัน การ​ประมวลผ​ ล​บรรทัด​ท่ี 3 ใช้เ​วลา​เป็น 2 หน่วย​เวลา
บรรทัดท​ ่ี 4 ประกอบ​ด้วย การ​ประมวล​ผล​การ​คูณ​คิด​เป็น 1 หน่วย​เวลา และ​การ​ให้​ผล​คูณ​ท่ี​ได้​กับ​ตัวแปร
multiply คิดเ​ป็น​อีก 1 หน่วย​เวลา ดัง​นั้น การ​ประมวล​ผลบ​ รรทัด​ท่ี 4 ใช้เ​วลาเ​ป็น 2 หน่วย​เวลา