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

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

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

Procedure sum(n)
1 BEGIN
2 IF n = 0 DO
3 RETURN 0
4 ELSE
5 RETURN n + sum(n — 1)
6 END

วิธี​ท�ำ
บรรทัดท​ ่ี 2 มีก​ าร​เปรียบเ​ทียบ​เงื่อนไข คิดเ​ป็น 1 หนว่ ยเ​วลา
บรรทัดท​ ่ี 3 ถ้าเ​ง่ือนไข​ในบ​ รรทัด​ที่ 2 เป็น​จริง จะ​มีก​ ารค​ ืนค​ ่า คิดเ​ป็น 1 หน่วย​เวลา
บรรทัดท​ ่ี 4 ถ้าเ​ง่ือนไขใ​น​บรรทัด​ที่ 2 เป็น​เท็จ ให้ท​ �ำบ​ รรทัด​ท่ี 5
บรรทัดท​ ี่ 5 มีก​ ารค​ ืนค​ ่า​การป​ ระมวลผ​ ล​การ​บวก n กับ sum(n-1) คิด​เป็น 1 + T(n – 1) หน่วยเ​วลา
ดังน​ ั้น รวม​ท้ังหมดจ​ ะใ​ช้เ​วลา T(n) = 1 + 1 + 1 + T(n — 1) = T(n — 1) + 3
จะเ​ห็น​ว่า T(0) = 0
T(1) = T(0) + 3 = 3 = 3 × 1
T(2) = T(1) + 3 = 6 = 3 × 2
T(3) = T(2) + 3 = 9 = 3 × 3
T(4) = T(3) + 3 = 12 = 3 × 4
…
ดัง​น้ัน T(n) = 3 × n = 3n = O(n)

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

FOR i := 1 to n DO
FOR j := 1 to i DO
Sum := Sum + 1

วธิ ที​ �ำ
ส่วนข​ องโ​ปรแกรม​น้ี เป็น​การท​ �ำลูป for ซ้อน​ใน 2 ลูป

การป​ ระมวลผ​ ลส​ ่วน​ในส​ ุดข​ อง​ลูป for ซ้อนก​ ัน คือ Sum := Sum + 1 ซ่ึง​มี​การ​ด�ำเนิน​การ​ท้ังหมด 2 อย่าง คือ
การ​บวกแ​ ละ​การ​ให้ค​ ่า คิดเ​ป็น 2 หน่วย​เวลา
ดังน​ ั้น จา​กลูป for ซ้อนใ​น จะไ​ด้การ​ประมวลผ​ ล​ทั้งหมด คิด​เป็น n i 2 หน่วยเ​วลา

iΣ=1 jΣ=1