Page 48 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 48
2-38 โครงสร้างข้อมูลและขั้นตอนวิธี
ข้อมูลม ีข นาดใหญ่ โดยให้พ ิจารณาปัญหาต่อไปน ี้
1. ปญั หาก ารหาผลรวมท มี่ ากทสี่ ุดข องล �ำ ดบั ย ่อย
ปัญหาการหาผลรวมท่ีมากที่สุดของล�ำดับย่อย (maximum subsequence sum problem) คือ การหา
ผ ลร วมข องล �ำดับย ่อยท ี่ให้ผ ลร วมม ากท ี่สุดจ ากล �ำดับข องจ �ำนวนเต็มท ี่ก �ำหนดให้ เป็นป ัญหาห นึ่งท ี่น ่าส นใจแ ละอ ธิบาย
ไว้ในหนังสือที่แต่งโดย Mark Allen Weiss (ในหนังสือ “Data Structures and Algorithm Analysis in C”)
จึงได้น�ำมาเป็นตัวอย่างเพื่อให้ได้ศึกษากันอย่างกว้างขวางและเข้าใจการเปรียบเทียบประสิทธิภาพของขั้นตอนวิธี
มากย ่ิงขึ้น ดังต ่อไปนี้
น้ีท ่ีม ีค่ามกากลท่าว่ีสคุดือนถ่ัน้าคกือ�ำหกนาดรหล �าำดคับ่ามขาอกงทจ่ีส�ำนุดวขนอเงต็มkΣ=nA11,AAk2, …, An ปัญหาค ือการห าผ ลรวมล�ำดับย ่อยใดๆ ของล �ำดับ
เช่น ถ้าข ้อมูลเข้า คือ ล�ำดับต่อไปน ้ี 2, -3, 1, 4
ล�ำดับย่อยท ี่เป็นไปได้ท้ังหมด ได้แก่
ล�ำดับย ่อยท ่ีม ีส มาชิกตัวเดียว ได้แก่
2 ผลรวมของล �ำดับย ่อยน้ีคือ 2
หรือ -3 ผลรวมข องล�ำดับย่อยนี้คือ -3
หรือ 1 ผลร วมข องล�ำดับย่อยน ้ีค ือ 1
หรือ 4 ผลรวมของล�ำดับย่อยน ี้คือ 4
ล�ำดับย ่อยท่ีมีสมาชิก 2 ตัว ได้แก่
2, -3 ผลรวมข องล �ำดับย่อยน ี้คือ 2 + (-3) = -1
หรือ -3, 1 ผลร วมข องล�ำดับย ่อยนี้ค ือ (-3) + 1 = -2
หรือ 1, 4 ผลร วมของล �ำดับย่อยน ้ีคือ 1 + 4 = 5
ล�ำดับย ่อยท่ีมีส มาชิก 3 ตัว ได้แก่
2, -3, 1 ผลรวมของล�ำดับย่อยน ี้คือ 2 + (-3) + 1 = 0
หรือ -3, 1, 4 ผลร วมข องล �ำดับย ่อยน้ีค ือ (-3) + 1 + 4 = 2
ล�ำดับย ่อยท ่ีมีสมาชิก 4 ตัว คือ 2, -3, 1, 4 ผลร วมข องล�ำดับย ่อยนี้ค ือ 2 + (-3) + 1 + 4 = 4
จะเห็นว่า ผลรวมของล�ำดับย่อย 1, 4 มีค่าเท่ากับ 5 มีค่ามากท่ีสุด (คือมากกว่าผลรวมของสมาชิกในแต่ละ
ล�ำดับย่อยอ่ืน) ดังนั้น ล�ำดับย่อย 1, 4 จึงเป็นค�ำต อบข องป ัญหาส�ำหรับล�ำดับท ่ีก�ำหนดให้ในตัวอย่างนี้น ั่นเอง
2. ข้ันตอนวิธีส�ำ หรับป ัญหาก ารหาผลรวมที่ม ากท่ีสุดของล �ำ ดับย อ่ ย
ในก ารแ ก้ป ัญหาน ี้ มีข ้ันต อนว ิธดี ้วยก ันห ลายแ บบ ซ่ึงแ ต่ละว ิธีต ่างก ็ให้ป ระสิทธิภาพท ี่แตกต ่างก ันอ อกไป โดย
Mark Allen Weiss ได้แนะน�ำไว้ท ั้งหมด 4 ขั้นตอนว ิธี ดังนี้
ข้ันตอนว ิธีท ี่ 1 ใช้เวลาในก ารป ระมวลผ ลเป็น O(n3)
ขั้นตอนว ิธีที่ 2 ใช้เวลาในการป ระมวลผลเป็น O(n2)
ขั้นตอนวิธีที่ 3 ใช้เวลาในก ารป ระมวลผ ลเป็น O(n log n)
ขั้นตอนวิธีที่ 4 ใช้เวลาเป็น O(n) เท่านั้น ซ่ึงถ ือว่าเร็วที่สุดในบ รรดาขั้นตอนว ิธีท ้ังหมด
เวลาจริงที่ใช้ประมวลผลแต่ละขั้นตอนวิธีแสดงไว้ในตารางที่ 2.3 จะเห็นว่า ส�ำหรับข้อมูลเข้าขนาดเล็ก
ทุกขั้นตอนวิธีสามารถประมวลผลได้อย่างรวดเร็ว ดังนั้น ถ้าคาดว่าข้อมูลจะมีขนาดเล็ก ก็ไม่จ�ำเป็นต้องออกแบบขั้น
