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

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

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

Procedure MaxSubSequenceSum(A1, A2, …, An)

1 BEGIN

2 ThisSum := 0 /* ให้​ค่าเ​ริ่ม​ต้น​ของ​ผลร​ วมล​ ำ�ดับย​ ่อย ThisSum เป็น 0 */

3 MaxSum := 0 /* ให้​ค่าเ​ริ่ม​ต้นข​ อง​ผลร​ วม​มากท​ ี่สุด MaxSum เป็น 0 */

4 FOR j := 1 to n DO /* ลูป for เพื่อเ​ป็นด​ ัชนี​อ้างอิง​ข้อมูล​แต่ละต​ ัว​ใน​ลำ�ดับ */

5 BEGIN

6 ThisSum = ThisSum + Aj /* หา​ผลร​ วม​ของล​ ำ�ดับ​ย่อย */

7 IF ThisSum > MaxSum THEN /* ตรวจส​ อบ​ผล​รวมย​ ่อยเ​พื่อห​ า​ผล​รวมท​ ี่ม​ าก​ที่สุด */

8 MaxSum := ThisSum

9 ELSE IF ThisSum < 0 /* ถ้าผ​ ล​รวมย​ ่อย​น้อย​กว่าศ​ ูนย์ ให้​เริ่มห​ าผ​ ล​รวมใ​หม่ */

10 ThisSum = 0

11 END

12 RETURN MaxSum /* คืน​ค่าผ​ ลร​ วม​ที่ม​ ากท​ ี่สุด */

13 END

จากก​ าร​ประม​ าณบ​ ิ๊กโ​อข​ องข​ ้ันต​ อนว​ ิธีท​ ้ัง 4 ท่ีก​ ล่าวม​ าน​ ้ี สามารถป​ ระมาณเ​วลา​หรือป​ ระสิทธิภาพข​ องข​ ั้น​ตอน​
วิธี ถ้าม​ ี​ข้อมูลท​ ั้งหมด 1,000 ข้อมูล ได้​ดังน้ี

ขน้ั ​ตอน​วิธ​ีที่ 1 มีป​ ระสิทธิภาพ​เป็น O(n3)
ใช้ก​ ารด​ �ำเนิน​การห​ รือ​เวลาท​ ้ังหมด​ประมาณ 1000 × 1000 × 1000 = 109 หน่วยเ​วลา
ข้นั ต​ อนว​ ธิ ​ีท่ี 2 มีป​ ระสิทธิภาพเ​ป็น O(n2)
ใช้ก​ ารด​ �ำเนิน​การ​หรือเ​วลา​ท้ังหมดป​ ระมาณ 1000 × 1000 = 106 หน่วยเ​วลา