Page 51 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 51
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-41
ข้ันตอนวธิ ีที่ 3 พิจารณาการหาผลรวมล�ำดับย่อย โดยอาศัยเทคนิคการเวียนเกิดและเทคนิคการแบ่งแยก
และเอาชนะ (divide and conquer) โดยหลักการคือ การแบ่งข้อมูลออกเป็น 2 ส่วนเท่าๆ กัน แล้วแก้ปัญหากับ
ข้อมูลเหล่าน ้ันอย่างเวียนเกิด แล้วน �ำผ ลที่ได้จากท้ัง 2 ส่วนมารวมกัน หรือพ ิจารณาร ่วมก ัน ซึ่งท�ำให้มีการป ระมวลผล
ที่น้อยล งกว่าการแก้ปัญหาทั้งระบบไปในคราวเดียว
โดยปัญหาการหาผลรวมที่มากที่สุดของล�ำดับย่อย เม่ือแบ่งข้อมูลเป็น 2 ส่วนแล้ว ค�ำต อบสุดท้ายซ่ึงเป็น
ผ ลรวมท่ีมากท ่ีสุดท ี่เป็นไปได้คือค่ามากสุดระหว่างค ่า 3 ค่า ต่อไปน ้ี
1. ผลรวมที่มากท ี่สุดของล �ำดับย ่อยในค ร่ึงซ ้ายแ รก
2. ผลร วมท ี่มากที่สุดของล �ำดับย ่อยในค ร่ึงข วาห ลัง
3. ผลรวมที่มากที่สุดข องล �ำดับย่อยที่อยู่ร ะหว่างคร่ึงซ้ายแ ละครึ่งข วา
ซึ่งในกรณีที่ 3 ผลรวมที่มากที่สุดของล�ำดับย่อยจะหาได้จากการรวมผลรวมท่ีมากที่สุดในคร่ึงซ้ายท่ีมี
จ�ำนวนเต็มตัวสุดท้ายของครึ่งซ้ายไว้ด้วย กับผลรวมที่มากที่สุดในครึ่งขวาที่มีจ�ำนวนเต็มตัวแรกของครึ่งขวาไว้ด้วย
ดังตัวอย่างต ่อไปน ี้
คร่ึงซ ้าย ครึ่งข วา
8 -4 3 -2 -3 5 7 -1
ผลรวมล�ำดับย่อยที่ม ากที่สุดในครึ่งซ้าย คือ 7 (ผลร วมจ าก 8 ถึง 3)
ผลร วมล�ำดับย ่อยท ี่ม ากที่สุดในค รึ่งข วา คือ 12 (ผลรวมจ าก 5 ถึง 7)
ผลร วมล �ำดับย่อยที่ม ากที่สุดที่อยู่ระหว่างครึ่งซ้ายและครึ่งข วา โดยหา
ผลรวมล�ำดับย่อยที่มากที่สุดในคร่ึงซ้ายที่มีจ�ำนวนเต็มตัวสุดท้ายของคร่ึงซ้ายรวมอยู่ด้วย คือ 5
(ผลรวมจาก 8 ถึง -2)
ผลรวมล�ำดับย่อยที่มากที่สุดในครึ่งขวาท่ีมีจ�ำนวนเต็มตัวแรกสุดของครึ่งขวารวมอยู่ด้วย คือ 9
(ผลรวมจ าก -3 ถึง 7)
ดังน ั้น ผลร วมล�ำดับย่อยท ี่อยู่ต รงก ลางระหว่างครึ่งซ ้ายและค ร่ึงข วาข องล�ำดับ คือ 5+ 9 = 14 (ผลรวมจาก 8
ถึง 7)
เพราะฉะนั้น ผลรวมของล�ำดับย่อยที่มากท่ีสุดในล�ำดับตัวอย่างน้ี คือ ค่ามากที่สุดของผลรวมล�ำดับย่อยที่
มากที่สุดในค รึ่งซ้าย ผลรวมล�ำดับย่อยที่มากที่สุดในค รึ่งขวา และผลรวมล�ำดับย่อยที่อ ยู่ตรงกลางระหว่างครึ่งซ้ายและ
ครึ่งขวาข องล �ำดับ นั่นคือ Max(7, 12, 14) = 14
จากหลักการแ บ่งแยกและเอาชนะนี้ ข้ันตอนวิธีท ี่ 3 สามารถเขียนเป็นข้ันตอนวิธีได้ ดังน้ี
