Page 49 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 49
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-39
ตอนวิธีมาก สามารถเลือกใช้ขั้นตอนวิธีใดใน 4 ขั้นตอนวิธีนี้ก็ได้ แต่ในทางกลับกัน ส�ำหรับข้อมูลที่มีขนาดใหญ่
โปรแกรมท่ีประมวลผลข้อมูลขนาดเล็กได้เร็วนั้นอาจประมวลผลข้อมูลขนาดใหญ่ได้ช้ามากก็ได้ ท้ังน้ีเน่ืองจากในข้ัน
ตอนวิธีน ้ันๆ อาจมีการท �ำงานซ ํ้าซ้อนและไม่มีป ระสิทธิภาพ จากตารางท่ี 2.3 จะเห็นว่า เม่ือข้อมูลม ีขนาดใหญ่ ขั้นตอน
วิธีท ี่ 4 ท�ำงานได้รวดเร็วที่สุดซ ่ึงถ ือว่ามีป ระสิทธิภาพท ่ีสุด
ตารางท่ี 2.3 เวลาที่ใชป้ ระมวลผลขัน้ ต อนวธิ ตี ่างๆ ในก ารแ ก้ป ญั หาก ารหาค่าผ ลร วมมากท่สี ุดข องล�ำ ดบั ยอ่ ย (วนิ าท)ี
ขนาดของขอ้ มลู เข้า ขั้นตอนวธิ ที ่ี 1 ข้ันตอนวธิ ที ี่ 2 ข้ันตอนวิธีที่ 3 ขัน้ ตอนวธิ ที ่ี 4
(n) O(n3) O(n2) O(n log n) O(n)
10 0.00103 0.00045 0.00066 0.00034
100 0.47015 0.01112 0.00486 0.00063
1,000 488.77 1.1233 0.05843 0.0033
10,000 111.13 0.68631 0.03042
ไม่สามารถหาค่าได้ 0.29832
100,000 ไม่สามารถหาค่าได้ ไม่สามารถหาค่าได้ 8.0113
ทม่ี า: Mark Allen Weiss, Data Structures and Algorithm Analysis in C, 2008.
ขัน้ ต อนวิธที ่ี 1 พิจารณาต รวจส อบท ุกล �ำดับย่อยท ่ีเป็นไปได้ โดย อาศัยลูป for ทั้งหมด 3 ลูป จึงท �ำให้ข้ันต อน
วิธีน ้ีใช้เวลาในก ารประมวลผ ลเป็น O(n3)
ลูป for แรก เพื่อให้ i เป็นด ัชนีช ี้ต�ำแหน่งเริ่มต ้นข องล�ำดับย่อย ซ่ึง i มีค ่าท่ีเป็นได้ต้ังแต่ 1 ถึง n
ลูป for ที่ 2 ซ้อนอยู่ภายในลูป for แรก เพื่อให้ j เป็นดัชนีช้ีต�ำแหน่งของล�ำดับย่อย ซ่ึง j มีค่าท่ีเป็นได้ต้ังแต่
1 ถึง n เช่นกัน เช่น เมื่อ i เป็น 3 และ j เป็น 5 ล�ำดับย ่อยท่ีก �ำลังพ ิจารณาคือ ล�ำดับย ่อยต ้ังแต่ล �ำดับท ่ี 3 ถึง 5 นั่นเอง
ลูป for ที่ 3 ซ้อนอ ยู่ภายในลูป for ที่ 2 เพ่ือให้ k เป็นด ัชนีช ้ีต�ำแหน่งของข ้อมูลในล �ำดับย่อยท ีละต ัว ดังน ้ัน k
j
มีค่าที่เปน็ ได้ต้ังแต่ i ถึง j เพอ่ื หาผลรวมค่าของข้อมูลในล�ำดับย่อยท่ีก�ำลังพิจารณา คอื ค�ำน วณหา Ak เช่น เมอื่ i
kΣ=i
เป็น 3 และ j เป็น 5 ล�ำดับย ่อยท ่ีก �ำลังพิจารณาคือ ล�ำดับย่อยต ั้งแต่ล �ำดับท่ี 3 ถึง 5 จึงห าผลร วมข ้อมูลต ้ังแต่ต �ำแหน่งที่
3 ถึง 5 ของอ าร์เรย์ไว้พ ิจารณา
จะเห็นว่า เมื่อเสร็จจากการหาผลรวม จึงน�ำผ ลรวมท่ีได้มาพิจารณาหาว่าผลรวมช่วงใดของล�ำดับท่ีให้ล�ำดับ
ย่อยท ่ีมีผลรวมมากที่สุด ซึ่งคือค�ำต อบที่ต ้องการน่ันเอง ข้ันตอนว ิธีท่ี 1 สามารถเขียนเป็นข้ันตอนวิธีได้ ดังนี้
