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

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

1) การ​เวยี น​เกดิ ​ท​มี่ ​กี าร​เรยี ก​ใช​แ้ บบ​กา​รวน​ลปู ​ธรรมดา เชน่ การ​ค�ำน​ วณ​คา่ ​แฟก​ทอ​เร​ยี ล ดงั ​ขน้ั ​ตอน​วธิ ​ตี อ่ ​ไป​น้ี

Procedure Factorial(n)
1 BEGIN
2 IF n ≤ 1 DO
3 RETURN 1
4 ELSE
5 RETURN n * Factorial(n — 1)
6 END

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

2) การเ​วียน​เกิด​ที่​มีก​ ารเ​รียก​ใช้​แบบ​ไม่ใช่ก​ าร​ วน​ลูปธ​ รรมดา แต่​เป็นการเ​รียก​ใช้ห​ ลายค​ รั้ง เป็นการอ​ อกแบบ​
ข้ัน​ตอน​วิธี​ช้ัน​สูง เช่น การแบ่งแยกและเอาชนะ (divide and conquer) การ​ค้นหา​แบบ​ทวิภาค (binary search)
รวม​ถึง​การ​เวียน​เกิด​ของ​ฟังก์ชัน​ฟิ​โบ​นัก​ซี (fibonacci) แต่ละ​ข้ัน​ตอน​วิธี​ท่ี​ใช้​การ​เวียน​เกิด​แบบ​น้ีอาจ​ท�ำให้​เวลา​ใน
ก​ าร​ประมวล​ผลด​ ีข​ ้ึน​หรือ​แย่ล​ งไ​ด้

ตวั อย่างท​ ี่ 2.19 จงห​ าฟ​ ังก์ชันเ​วลา T(n) ของโ​ปรแกรม​ต่อ​ไป​นี้ พร้อมท​ ้ัง​ประ​มาณบ​ ๊ิกโ​อ​ของ T(n)

Procedure Max(A1, A2, …, An)

1 BEGIN
2 max :i=:=A11
3 FOR to n DO
4 BEGIN
5 IF mmaxax<:=AiATi HEN
6
7 END
8 DISPLAY max
9 END

วธิ ี​ท�ำ
บรรทัดท​ ่ี 2 และ 8 มีก​ ารเ​รียก​ใช้​ตัว​ด�ำเนิน​การเ​พียง​หนึ่งต​ ัว​ใน​แต่ละบ​ รรทัด คดิ ​เปน็ 2 หนว่ ย​เวลา
บรรทัดท​ ่ี 3 เป็นล​ ูป for ที่​ซ่อน​การ​ท�ำงาน​ไว้ ซ่ึง​ใช้เ​วลาท​ ั้งหมด 2n + 2 หน่วย​เวลา
บรรทัดท​ ี่ 5 และ 6 ม​กี ารเ​ปรยี บเ​ทยี บ​และ​การ​ใหค​้ า่ เปน็ 2 หนว่ ย​เวลา ในลปู for ท�ำใหม​้ ​กี ารป​ ระมวลผล​
บรรทัด​ที่ 5 ท้ังหมด n คร้ัง และ​บรรทัด​ที่ 6 ทั้งหมด​มาก​ท่ีสุด​ประมาณ n คร้ัง​
เช่น​กัน ถ้า​เง่ือนไข​ใน​บรรทัด​ท่ี 5 เป็น​จริง​เสมอ ดัง​นั้น ใน​ส่วน​น้ี​จะ​ใช้​เวลา
2n หน่วย​เวลา
ดังน​ ั้น รวม​ทั้งหมดจ​ ะ​ใช้​เวลา T(n) = 2 + (2n + 2) + 2n = 4n + 4 = O(n)