Page 36 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 36
2-26 โครงสร้างข้อมูลและขั้นตอนวิธี
เรือ่ งท ่ี 2.2.1
การวเิ คราะหป์ ระสทิ ธภิ าพของขน้ั ตอนว ิธี
การวิเคราะห์ประสิทธิภาพของข้ันตอนวิธี สามารถวัดได้จากหลายอย่าง เช่น พิจารณาจากจ�ำนวนเน้ือที่
หน่วยค วามจ �ำท ่ีใช้ในก ารป ระมวลผ ลห รือพ ิจารณาจ ากค วามเร็วในก ารท �ำงานข องโปรแกรม ซึ่งก ารว ิเคราะห์ ประสิทธิ-
ภาพของขั้นตอนวิธีสามารถเขียนให้อยู่ในรูปหน่วยของเวลาท่ีใช้ในการประมวลผลข้อมูลใดๆ ได้ด้วยฟังก์ชัน T(n)
เมื่อ n เป็นจ �ำนวนเต็มที่แ ทนจ�ำนวนข ้อมูลท ี่จะประมวลผ ล
ในเร่ืองก่อนหน้าได้แนะน�ำแ นวคิดเกี่ยวกับข้ันตอนวิธีและการเปรียบเทียบการเติบโตของฟังก์ชันไว้แล้ว
ในเรื่องน ้ีจะศ ึกษาเร่ืองก ารน ับจ �ำนวนต ัวด �ำเนินก ารท ี่ใช้ในข ้ันต อนว ิธีเพื่อใช้ป ระมาณเวลาในก ารป ระมวลผ ลข ้อมูลแ ละ
เปรียบเทียบประสิทธิภาพของขั้นตอนวิธีต่างๆ ถึงแม้ว่าในความเป็นจริงเวลาที่ใช้ในการแก้ปัญหาจะไม่ได้ข้ึนอยู่กับ
จ�ำนวนตัวด�ำเนินการเพียงอย่างเดียว แต่ยังข้ึนอยู่กับปัจจัยอื่นๆ อีก เช่น ฮาร์ดแวร์และซอฟต์แวร์ท่ีใช้ประมวลผลโปร
แกร มน ั้นๆ ด้วย ดังนั้น เพื่อท ่ีจะป ระมาณเวลาท่ีใช้ประมวลผลข ้อมูลข นาด n ให้ได้ใกล้เคียงท ่ีสุด อาจประมาณค่าได้
จากผ ลค ูณของเวลาที่เคยใช้ในก ารประมวลผ ลกับค ่าค งต ัวหนึ่งๆ ได้ เช่น ในเคร่ืองซ ุปเปอร์คอมพิวเตอร์อาจแ ก้ปัญหา
ขนาด n ได้เร็วเป็นล้านๆ เท่าของเวลาท่ีใช้ประมวลผลด้วยเครื่องไมโครคอมพิวเตอร์ จะเห็นว่า ปัจจัยหน่ึงล้านเท่านี้
ไม่ได้ขึ้นอยู่กับขนาด n ของปัญหา แต่ขึ้นอยู่กับประสิทธิภาพเชิงกายภาพของเคร่ืองคอมพิวเตอร์ ดังนั้น
จึงใช้บิ๊กโอเข้ามาช ่วยในการประมาณเวลาในก ารประมวลผลข ้อมูลขนาด n ได้ การใช้บ๊ิกโอจะช ่วยประมาณการเติบโต
ของฟังก์ชัน T(n) ได้ โดยปราศจากข้อกังวลใดๆ เก่ียวกับตัวคูณค่าคงตัวหรือพจน์ที่มีอันดับตํ่ากว่า (กล่าวไว้ในเร่ือง
ท่ี 2.1.2) กล่าวอีกอ ย่างหน่ึงค ือ การใช้บ ๊ิกโอท �ำให้ไม่ต ้องก ังวลเก่ียวก ับฮ าร์ดแวร์หรือซอฟต์แวร์ท ี่ใช้ และย ่ิงไปก ว่าน ้ัน
การใช้บ ิ๊กโอยังส ามารถส มมติได้ว่า ตัวด�ำเนินก ารท ่ีแ ตกต ่างก ันจะใช้เวลาเท่าก ันในก ารป ระมวลผล ซึ่งท�ำให้ง ่ายต่อการ
วิเคราะห์ป ระสิทธิภาพข องขั้นต อนวิธี
บิ๊กโอใช้กันมากในการประมาณค่าจ�ำนวนตัวด�ำเนินการที่ใช้ในขั้นตอนวิธีเมื่อข้อมูลเข้ามีข นาดใหญ่ข้ึน เพราะ
ช่วยให้สามารถตัดสินใจได้ว ่า ในท างปฏิบัติจะดีหรือไม่ท ่ีจะใช้ข ั้นตอนวิธีท ่ีเฉพาะเจาะจงหนึ่งๆ กับก ารแ ก้ปัญหาน ้ันๆ
เม่ือม ีข นาดของข ้อมูลเพิ่มขึ้น ย่ิงไปกว่านั้นบ๊ิกโอย ังช่วยให้สามารถเปรียบเทียบขั้นตอนว ิธี 2 ขั้นตอนวิธีได้ว ่า ข้ันต อน
วิธีไหนม ีประสิทธิภาพมากกว่าเมื่อขนาดของข้อมูลใหญ่ข้ึน เช่น ถ้าม ีข ั้นต อนวิธี 2 ข้ันต อนในก ารแก้ป ัญหาปัญหาหนึ่ง
ข้ันตอนวิธีหนึ่งใช้ตัวด�ำเนินการท้ังหมด 100n2 + 17n + 4 ตัว และอีกขั้นตอนวิธีหน่ึงใช้ n3 ตัว บ๊ิกโอสามารถช่วย
ให้เห็นชัดเจนว่า ข้ันตอนวิธีแรกใช้ตัวด�ำเนินการน้อยกว่าขั้นตอนวิธีหลังมากเม่ือขนาดของข้อมูล n มีขนาดใหญ่มาก
ถึงแ ม้ว่าในขณะท่ี n มีข นาดเล็ก เช่น n = 10 ข้ันตอนว ิธีแ รกจ ะใช้ตัวด�ำเนินการม ากกว่าก ็ตาม แต่ก ารป ระมวลผ ลข้อมูล
ขนาดใหญ่ได้อ ย่างร วดเร็วย ่อมมีความส �ำคัญม ากกว่า
1. การป ระมาณเวลาทใี่ชป้ ระมวลผล
การป ระมาณเวลาท ี่ใช้ป ระมวลผ ลข องข ั้นต อนว ิธี สามารถป ระมาณได้โดยก ารน ับจ �ำนวนต ัวด �ำเนินก ารท ี่ใช้ใน
ข้ันตอนวิธี ด้วยก ารสมมติว่า ตัวด�ำเนินก ารต่างๆ จะใช้เวลาเท่ากันในก ารท�ำงาน ตัวด �ำเนินการท ี่พ ูดถึงน ้ี เช่น การบวก
(+) การลบ (—) การคูณ (*) การหาร (/) หรือแม้แต่การให้ค่า (:=) และการเปรียบเทียบต่างๆ (==, < หรือ >) เป็นต้น
จะเห็นว่า ในขั้นตอนวิธีมีการเรียกใช้ตัวด�ำเนินการต่างๆ มากมาย เพื่อค�ำนวณให้ได้ผลลัพธ์ตามท่ีต้องการ ไม่ว่าจะ
เป็นการหาค่าเฉล่ีย ขั้นตอนวิธีจะมีการเรียกใช้การบวกตัวเลขต่างๆ เข้าด้วยกันและท�ำการหารค่าที่ได้
