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

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

บรรทัด​ท่ี 5 ประกอบด​ ้วย การป​ ระมวลผ​ ลก​ าร​บวกค​ ิด​เป็น 1 หน่วย​เวลา และ​การ​หาร​ผล​บวกท​ ี่ไ​ด้ค​ ิด​เป็น​อีก
1 หน่วยเ​วลา จากน​ ั้นน​ �ำผ​ ล​หารท​ ่ีไ​ด้ใ​ห้ก​ ับต​ ัวแปร average คิดเ​ป็น​อีก 1 หน่วย​เวลา ดัง​นั้น การ​
ประมวล​ผลบ​ รรทัดท​ ี่ 5 ใช้เ​วลา​เป็น 3 หนว่ ยเ​วลา

ดังน​ ้ัน การ​ประมวล​ผล​การ​ท�ำงานท​ ั้ง 5 บรรทัด ใช้เ​วลา​รวมก​ ันเ​ท่ากับ 1 + 1 + 2 + 2 + 3 = 9 หนว่ ยเ​วลา

ตวั อยา่ งท​ ่ี 2.18 จงป​ ระมาณเ​วลาท​ ี่ใ​ช้ใ​นก​ ารป​ ระมวลผ​ ล เพ่ือค​ �ำนวณผ​ ลร​ วม n i3 ซึ่งส​ ามารถเ​ขียนเ​ป็นข​ ้ันต​ อนว​ ิธีไ​ด​้
ดังน้ี
iΣ=1

Procedure sum3(n)
1 BEGIN
2 sum := 0
3 FOR i := 1 to n DO
4 BEGIN
5 sum := sum + (i*i*i)
6 END
7 RETURN sum
8 END

วธิ ีท​ �ำ
จากข​ ั้น​ตอน​วิธีข​ ้าง​ต้น สามารถ​วิเคราะห์เ​วลา​ในก​ ารป​ ระมวล​ผล​ได้ด​ ังนี้
บรรทัด​ที่ 2 เป็นการ​ให้ค​ ่าข​ ้อมูล​กับ​ตัวแปร sum คิด​เป็น 1 หน่วยเ​วลา
บรรทัดท​ ี่ 3 เป็น​ค�ำส​ ั่งท​ �ำซ​ �้ำ for ที่​มีก​ ารป​ ระมวลผ​ ลภ​ ายในซ​ ่อน​อยู่ คือ
- การ​ให้​ค่าเ​ริ่มต​ ้นก​ ับต​ ัวแปร i คิด​เป็น 1 หน่วย​เวลา
- ก าร​ตรวจ​สอบ​โดย​การ​เปรียบ​เทียบ i ≤ n คิด​เป็น 1 หน่วย​เวลา แต่​จะ​มี​การ​เปรียบ​เทียบ​ไป​
เร่ือยๆ จน​ค่า i มากกว่า n ดัง​น้ัน จะ​มี​การ​เปรียบ​เทียบ​ท้ังหมด n + 1 ครั้ง คิด​เป็น n + 1
หน่วยเ​วลา
- การ​เพิ่ม​ค่า​ของ i ที​ละ 1 คิด​เป็น 1 หน่วย​เวลา โดย​จะ​มี​การ​เพ่ิม​ค่า i ไป​เร่ือยๆ จนถึง n
ดัง​นั้น มีก​ าร​เพ่ิมค​ ่า​ของ i ท้ังหมด n คร้ัง คิด​เป็น n หน่วย​เวลา
ดัง​น้ัน เวลา​ที่ใ​ช้​ท้ังหมด​ในส​ ่วน​น้ี​คือ 1 + (n + 1) + n = 2n + 2 หน่วยเ​วลา
บรรทัดท​ ี่ 4 เป็นการ​แสดงส​ ่วนเ​ริ่มท​ �ำซ​ ้ําของ​ลูป for ไม่มี​การป​ ระมวล​ผล
บรรทัด​ท่ี 5 เปน็ ​ค�ำส​ ่ัง​ท​ี่ให้​กระท�ำภ​ าย​ในลูป for ซงึ่ ​จะ​กระท�ำบ​ รรทัด​น​ี้ทงั้ หมด n ครงั้ (ตาม​เงอื่ น​ไข​ในลปู for)
โดย​ค�ำ​ส่ัง​ใน​บรรทัด​น้ี​มี​การ​คูณ 2 ครั้ง การ​บวก 1 คร้ัง การ​ให้​ค่า​ผล​บวก​กับ​ตัวแปร sum
อีก 1 คร้ัง รวม​เป็น 4 หน่วย​เวลา และ​เนื่องจาก​มี​การ​ประมวล​ผล​บรรทัด​น้ี​ท้ังหมด n ครั้ง
ดัง​นั้น จะใ​ช้เ​วลาป​ ระมวลผ​ ลใ​นส​ ่วน​นี้​ทั้งหมด​คิด​เป็น 4n หนว่ ย​เวลา
บรรทัดท​ ่ี 6 เป็นการแ​ สดงส​ ่วน​สิ้นส​ ุด​การท​ �ำซ​ ํ้าของ​ลูป for ไม่มีก​ ารป​ ระมวล​ผล
บรรทัด​ที่ 7 เป็นการค​ ืนค​ ่า​ของก​ ารป​ ระมวลผ​ ล คิดเ​ป็น 1 หนว่ ย​เวลา
เพราะ​ฉะนัน้ การ​ประมวล​ผล​การ​ท�ำงาน​ของ​ข้ัน​ตอน​วิธี​น​ี้ใช​้เวลา​รวม​กัน​เป็น 1 + (2n + 2) + 4n + 1 = 6n + 4

หนว่ ย​เวลา หรือเ​ขียนแ​ ทนด​ ้วย ฟังก์ชัน T(n) จะไ​ด้ว​ ่า T(n) = 6n + 4 น่ันเอง