Page 47 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 47
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-37
หมายเหตุ:
ในกิจกรรมข้อ 1 นี้ ถ้าโจทย์กำ�หนดให้หาบ๊ิกโอ สามารถใช้กฎการหาบิ๊กโอ จะทำ�ให้การประมาณบิ๊กโอทำ�ได้
รวดเร็วและถ ูกต อ้ ง
2. จากก ฎก ารหาบ ๊กิ โอ ฟังก์ชนั เวลาของข ้ันต อนว ิธี MinMax เป็น O(n)
3. จากกฎการห าบ ิ๊กโอ ฟงั กช์ นั เวลาของขัน้ ต อนวิธี EvenOrOdd เปน็ O(1)
4. จากก ฎก ารห าบ กิ๊ โอ ฟังก์ชนั เวลาของขน้ั ตอนวธิ ี Evalutaion เป็น O(n)
เรอ่ื งท่ี 2.2.2
การเปรยี บเทยี บประสทิ ธิภาพข องข ้ันตอนว ิธี
การวิเคราะห์เวลาที่ใช้ประมวลผลโปรแกรมนั้น มีหลายปัจจัยท่ีมีผลกระทบต่อเวลาท่ีใช้ประมวลผล เช่น
ตัวคอมไพเลอร์ (compiler) และเคร่ืองคอมพิวเตอร์ ซ่ึงปัจจัยเหล่าน้ีมีผลต่อการประมวลผลอย่างเห็นได้ชัด แต่จะ
เกินขอบเขตก ารพ ิจารณาในท างท ฤษฎี เน่ืองจากเป็นป ัจจัยท ี่จัดการได้ยาก ดังนั้น ปัจจัยห ลักอ ีกอย่างห นึ่งท่ีส�ำคัญ คือ
ขั้นต อนวิธีท ่ีใช้และข้อมูลเข้า ที่สามารถพ ิจารณาได้จ ากขนาดของข ้อมูลเข้าเป็นห ลัก
การวิเคราะห์เวลาในบางคร้ัง จะเห็นว่า มีการประเมินเวลาที่เกินความจริง ซ่ึงสามารถแบ่งการวิเคราะห์เวลา
ท่ีใช้ประมวลผลได้เป็น 3 กรณี ได้แก่ เวลาที่ใช้ประมวลผลกรณีท่ีดีที่สุด (best-case running time) เวลาท่ีใช้
ประมวล-ผลกรณีท่ีแย่ท่ีสุด (worst-case running time) และเวลาที่ใช้ประมวลผลกรณีเฉล่ีย (average running
time)
เวลาท่ีใช้ประมวลผลกรณีที่ดีที่สดุ (best-case running time) หมายถึง เวลาท่ีใช้ประมวลผลเร็วท่ีสุด
เมื่อข ้อมูลม ีร ูปแ บบที่ท�ำให้การประมวลผลของข ั้นตอนว ิธีท ่ีได้อ อกแบบไว้ส�ำเร็จได้อย่างร วดเร็วท่ีสุด
เวลาที่ใช้ประมวลผลกรณีที่แย่ท่ีสุด (worst-case running time) หมายถึง เวลาท่ีใช้ประมวลผลนานท่ีสุด
เม่ือข้อมูลมีรูปแบบท่ีท�ำให้การประมวลผลของข้ันตอนวิธีท่ีได้ออกแบบไว้ส�ำเร็จได้ช้า อาจเป็นเพราะการจัดเรียงข้อมูล
ท่ีไม่เอ้ือประโยชน์แก่ก ารประมวลผลของข ั้นต อนว ิธีท ่ีได้ออกแบบไว้
เวลาท ใี่ ชป้ ระมวลผลก รณเี ฉลย่ี (average-case running time) หมายถึง เวลาท ่ีใช้ประมวลผ ลโดยเฉลี่ยส�ำหรับ
ข้อมูลใดๆ ท่ีส ามารถค าดหวังได้ เม่ือข ้อมูลมีร ูปแ บบต่างๆ
กรณีเฉลี่ยอาจถือว่าเป็นการวิเคราะห์ท่ีใกล้เคียงความเป็นจริงมากที่สุด ซึ่งโดยปกติจะได้ค่าประมาณท่ีอาจ
จะมากกว่ากรณีท่ีดีท่ีสุดแ ละจะน้อยก ว่าก รณีท่ีแ ย่ท ่ีสุดเสมอ แต่กรณีท่ีแย่ท่ีสุดถือเป็นการป ระมาณเวลาที่ใช้ม ากท ี่สุด
ที่อาจจ ะเป็นไปได้ข องข ้ันต อนว ิธีน ้ันๆ น่ันเอง ส�ำหรับข ั้นต อนว ิธีท ี่ม ีความซ ับซ ้อนท ั้งห ลาย ขอบเขตข องเวลาท ่ีใช้ในก าร
ประมวลผ ลในกรณีที่แย่ที่สุด สามารถห าได้โดยก ารใช้ข้อมูลเข้าท่ีไม่ดี ซึ่งโดยป กติแล้วจะเป็นการประเมินค่าเกินจริง
แต่ปัญหาส ่วนใหญ่ การวิเคราะห์กรณีเฉลี่ยจะมีค วามซับซ้อน เช่น มีห ลายก รณีท ่ีไม่ส ามารถห าได้ ท�ำให้การวิเคราะห์
ขอบเขตในกรณีท ี่แย่ที่สุดเป็นผลก ารวิเคราะห์ที่ดีท่ีสุดท่ีจ ะท �ำได้ในการประเมินป ระสิทธิภาพข องขั้นตอนว ิธี
ในเร่ืองนี้จะอธิบายการเปรียบเทียบประสิทธิภาพของข้ันตอนวิธีท่ีแตกต่างกันที่ใช้ในการแก้ปัญหาเดียวกัน
โดยพิจารณาการหาข อบเขตในก รณีเฉลี่ยของแ ต่ละขั้นตอนวิธี เพ่ือให้เห็นตัวอย่างที่ชัดเจนว่าป ัญหาห น่ึงๆ อาจแก้ได้
ด้วยวิธีการหลากหลายวิธี และวิธีการไหนจะให้การประมวลผลท่ีรวดเร็วท่ีสุด (มีประสิทธิภาพท่ีสุด) เมื่อขนาดของ
