Page 53 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 53
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-43
จากรหัสเทียมของข้ันตอนวิธีที่ 3 จะมี 2 โพรซีเยอร์ในการท�ำงาน โดยโพรซีเยอร์แรก MaxSubSequence-
Sum() จะรับข้อมูลเข้ามาโดยตรง แล้วเรียกใช้โพรซีเยอร์ท่ี 2 คือ MaxSubSum() ท่ีมีการระบุต�ำแหน่งเร่ิมต้นและ
สุดท้ายของล�ำดับเพ่ือพิจารณาหาค่าผลรวม ที่ท�ำเช่นน้ีเนื่องจากจะมีการเรียกใช้การท�ำงานในลักษณะเดิมกับข้อมูล
ในล �ำดับเดิมแต่ต่างต �ำแหน่งกัน จึงต ้องเพิ่มก ารระบุต �ำแหน่งเร่ิมต ้นและสุดท้ายของล�ำดับย ่อยที่ก�ำลังจ ะค �ำน วณด ้วย
โพรซีเยอร์ MaxSubSum() จะเร่ิมต้นโดยการพิจารณาว่าจุดเร่ิมต้นและสุดท้ายของล�ำดับย่อย (ในท ่ีน่ีแทน
ด้วย Left และ Right ตามล�ำดับ) เป็นจุดเดียวกันหรือไม่ ถ้าใช่ให้คืนค่าที่มากกว่า 0 เพราะต ้องการหาผลรวมท่ีมาก
ท่ีสุด
แต่ถ้าไม่ใช่ต �ำแหน่งเดียวกัน จะสามารถท�ำงานแบ่งข้อมูลออกเป็น 2 ส่วนได้ โดยห าจุดก่ึงกลางจาก Center
:= ⎣(Left + Right)/2⎦ เป็นการป ัดเศษจากก ารห ารลง แล้วเรียกใช้ MaxSubSum() เพ่ือค�ำนวณหาผ ลร วมล�ำดับย ่อย
ที่ม ากสุดของทั้ง 2 ส่วน
จากน ั้นค �ำน วณค่าผลร วมท ีม่ ากทีส่ ดุ ของล�ำดบั ย อ่ ยทอ่ี ยรู่ ะหว่างคร่ึงซา้ ยแ ละครึ่งขวา จะไดเ้ ท่ากับ (MaxLeft-
BorderSum + MaxRightBorderSum) แล้วพิจารณาห าค ่าม ากส ุดร ะหว่าง ค่ามากท่ีสุดของผลรวมล�ำดับย่อยท่ีม าก
ที่สุดในครึ่งซ้าย (MaxLeftSum) ผลรวมล�ำดับย่อยที่มากที่สุดในคร่ึงขวา (MaxRightSum) และผลรวม
ล�ำดับย่อยที่อยู่ตรงกลางระหว่างครึ่งซ้ายและคร่ึงขวา (MaxLeftBorderSum + MaxRightBorderSum) ในค�ำส ่ัง
สุดท้ายค ือค�ำส ั่ง RETURN ค�ำต อบท ี่หาได้นั่นเอง
การวิเคราะห์หาเวลาที่ใช้ในการประมวลผล ท�ำได้ในลักษณะเดียวกันกับการค�ำน วณฟิโบนักซี โดยให้ T(n)
เป็นเวลาท่ีข ้ันตอนว ิธีใช้แ ก้ป ัญหาขนาด n
ถ้า n = 1 แล้วโปรแกรมจะใช้เวลาเป็นค ่าคงตัวคือ T(1) = 1 หน่วยเวลา
ส�ำหรับ n > 1 โปรแกรมจะประมวลผลการเวียนเกิด 2 ครั้ง (จากรหัสเทียม คือ เพ่ือหา MaxLeftSum และ
Mจทะี่มaใีxชจR้เ�ำวiนgลวhานt2SเTuต(m็มn2ต)โ ด ัวแยสลกุดะามทรีเก้ารยาียรกแใฟชล้ลังะกูปผ์ชลfันoรrMว2มaคxมรSา้ังuกbโทดSี่สยuุดไmมใ(่นใ)ชแค้ บfรoบึ่งrขเวซวีย้อานนทเี่กมกันิดีจ)�เำนพซวึ่ง่ือตนห่าเาตงคใ็มช่าตเ้เรวัว่ิมลแาตรเป้นก็นผ(จลTาร(กวn2รม)หมหัสานกเ่วททยียี่สเมวุดลใคานือรควเรพมึ่ง่ือแซลห้าย้วา
MaxLeftBorderSum และ MaxRightBorderSum) ซึ่งใ ช้เวลามากที่สุดเป็น O(n) ดังนั้น ขั้นตอนวิธีน้ีจะใช้เวลา
ท ั้งหมด เป็น 2TT((n21)) =+1O(n) ซึ่งได้แก่ส มการ ดังต ่อไปนี้
เพื่อง ่าTย(แnก)่ก=าร2คT�ำ(นn2ว)ณ+
12Tแ(ลn2้ว) O(n) O(n) ในส มการข้างบ นด้วย n เพื่ออธิบาย T(n) จะได้
ให้แทนที่
T(n) = + n
T(1) =
ซึ่ง
T(2) = 4 = 2*2
T(4) = 12 = 4*3
T(8) = 32 = 8*4
T(16) = 80 = 16*5
ไปเรื่อยๆ จะเห็นว ่ามีรูปแบบท่ีสัมพันธ์ก ับ n โดยที่เม่ือ n = 2k จะได้ log2 n = k
