Page 39 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 39
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-29
จากตัวอย่างท่ี 2.18 นี้ จะเห็นว่า ขั้นตอนวิธีน้ีใช้เวลาเป็นฟังก์ชัน T(n) ท่ีข้ึนอยู่กับขนาดของข้อมูล n เป็น
T(n) = 6n + 4 ถ้าใช้ความรู้เร่ืองการเติบโตของฟังก์ชันที่ได้ศึกษาผ่านมาแล้ว จะสามารถประมาณบิ๊กโอของ T(n) นี้
ไดว้ า่ เปน็ O(n) ซง่ึ ห มายความวา่ ขน้ั ต อนวธิ นี จ้ี ะม กี ารเตบิ โตของเวลาท ใี่ ชใ้ นการประมวลผ ลนอ้ ยกวา่ ห รอื เทา่ กบั อ นั ดบั n
การวิเคราะห์โปรแกรมด้วยการนับจ�ำนวนตัวด�ำเนินการอย่างละเอียดแบบนี้ ในบางข้ันตอนวิธีท่ีมีความ
ซ ับซ ้อนแ ละม ีการท �ำงานห ลายข ั้นต อนม าก อาจท �ำให้ก ารนับแบบน ี้เป็นไปไม่ได้ แต่ถ้าพ ิจารณาให้ค �ำต อบอ ยู่ในรูปของ
บกิ๊ โอ สามารถใช้เทคนิคลดั มากมายในการหาบ ๊ิกโอไดโ้ ดยท่ีไม่มผี ลกร ะท บต อ่ ค�ำต อบทต่ี อ้ งการ เชน่ ในต วั อยา่ งที่ 2.18
เห็นได้ชัดว่าบรรทัดท่ี 5 เป็น O(1) ต่อการประมวลหนึ่งคร้ัง จึงไม่จ�ำเป็นต้องนับค่าที่แน่นอนว่ามีการประมวลผล
กี่ห น่วยเวลา (2 3 หรือ 4 หน่วยเวลา) และบ รรทัดท่ี 2 และ 7 เป็นบรรทัดที่ไม่ส �ำคัญในเร่ืองของเวลาเลยเม่ือเทียบกับ
การประม วลผ ลลูป for ในบรรทัดที่ 3 ดังน ั้น สามารถล ะการพิจารณาในส ่วนเหล่าน ้ีได้ และพ ิจารณาเฉพาะบรรทัดที่ 3
ซ่ึงเป็นล ูป for จะได้ T(n) = O(n) เช่นกัน
2. กฎในก ารว ิเคราะห์ขนั้ ตอนวธิ เี พอ่ื ป ระมาณบ กิ๊ โอ
กฎขอ้ ท ี่ 1 การวิเคราะหล์ ูป for
เวลาท่ีใช้ในการประมวลผลของลูป for หน่ึงๆ คือ เวลาท่ีใช้ประมวลผลค�ำส ั่งหรือตัวด�ำเนินการท้ังหมดท่ีอยู่
ในลูป for (รวมถึงการตรวจสอบและเปรียบเทียบ) คูณกับจ�ำนวนคร้ังท้ังหมดท่ีต้องวนท�ำซ้�ำ เช่น ส่วนของ
การประมวลผลต่อไปน้ี ใช้เวลาในก ารประมวลผลเป็น O(n)
sum := 0
FOR i := 0 to n DO
BEGIN
sum := sum + i
END
กฎข้อท่ี 2 การวิเคราะห์ลูป for ซ้อนใน
ลูป for ซ้อนใน (nested for-loop) คือ ลูป for ท่ีซ้อนๆ กันหลายๆ ลูป ให้วิเคราะห์เข้าไปทุกๆ ลูปภายใน
เวลาท่ีใช้ประมวลผลท้ังหมดของลูปซ้อน เป็นเวลาท่ีใช้ประมวลผลของค�ำส ั่งท้ังหมดคูณกับผลคูณของขนาดของ
ล ูปทุกลูป เช่น การประมวลผ ลย ่อยต่อไปน ี้ ใช้เวลาในการป ระมวลผ ลในร ะดับ O(n2)
FOR i := 0 to n DO
BEGIN
FOR j := 0 to n DO
BEGIN
k := k + 1
END
END
หมายเหต:ุ การว ิเคราะห์ล ูป while สามารถพ ิจารณาได้ในแ บบเดียวกันกับก ารวิเคราะห์ล ูป for
