อ่าน 2 นาที
กรณีที่ดีที่สุด กรณีที่แย่ที่สุด และกรณีเฉลี่ย
ใน วิทยาการคอมพิวเตอร์ กรณี ที่ดีที่สุด แย่ ที่สุด และ เฉลี่ย ของ อัลกอริทึม ที่กำหนด แสดงถึงการใช้ ทรัพยากร อย่างน้อยที่สุด มาก ที่สุด และ โดย เฉลี่ย ตามลำดับ...
กรณีที่ดีที่สุด กรณีที่แย่ที่สุด และกรณีเฉลี่ย
ในวิทยาการคอมพิวเตอร์กรณีที่ดีที่สุดแย่ที่สุดและเฉลี่ยของอัลกอริทึม ที่กำหนด แสดงถึงการใช้ทรัพยากรอย่างน้อยที่สุด มากที่สุดและโดยเฉลี่ย ตามลำดับโดยปกติทรัพยากรที่พิจารณาคือเวลาในการทำงาน กล่าวคือความซับซ้อนของเวลาแต่ก็อาจเป็นหน่วยความจำหรือทรัพยากรอื่นๆ ก็ได้ กรณีที่ดีที่สุดคือฟังก์ชันที่ดำเนินการจำนวนขั้นตอนน้อยที่สุดกับข้อมูลอินพุตที่มี n องค์ประกอบ กรณีที่แย่ที่สุดคือฟังก์ชันที่ดำเนินการจำนวนขั้นตอนมากที่สุดกับข้อมูลอินพุตที่มีขนาด n กรณีเฉลี่ยคือฟังก์ชันที่ดำเนินการจำนวนขั้นตอนโดยเฉลี่ยกับข้อมูลอินพุตที่มี n องค์ประกอบ[ 1 ]
ในการประมวลผลแบบเรียลไทม์ เวลา ในการประมวลผลในกรณีที่เลวร้ายที่สุดมักเป็นสิ่งที่น่ากังวลเป็นพิเศษ เนื่องจากจำเป็นต้องทราบว่าอาจต้องใช้เวลานานเท่าใดในกรณีที่เลวร้ายที่สุดเพื่อรับประกันว่าอัลกอริทึมจะเสร็จสิ้นตรงเวลาเสมอ
ประสิทธิภาพเฉลี่ยและประสิทธิภาพในกรณีที่เลวร้ายที่สุดเป็นสิ่งที่ใช้กันมากที่สุดในการวิเคราะห์อัลกอริทึม ส่วนประสิทธิภาพในกรณีที่ดีที่สุด นั้นพบได้น้อยกว่า แต่ก็มีประโยชน์เช่นกัน ตัวอย่างเช่น เมื่อทราบกรณีที่ดีที่สุดของแต่ละงานแล้ว ก็สามารถนำมาใช้เพื่อปรับปรุงความแม่นยำของการวิเคราะห์กรณีที่เลวร้ายที่สุดโดยรวมได้ นักวิทยาศาสตร์คอมพิวเตอร์ใช้เทคนิคการวิเคราะห์เชิงความน่าจะเป็น โดยเฉพาะอย่างยิ่ง ค่าที่คาดหวังเพื่อกำหนดเวลาการทำงานที่คาดหวัง
คำศัพท์เหล่านี้ถูกนำไปใช้ในบริบทอื่นๆ เช่น ผลลัพธ์ที่เลวร้ายที่สุดและดีที่สุดของการระบาดของโรค อุณหภูมิที่เลวร้ายที่สุดที่ชิ้นส่วนวงจรไฟฟ้าอาจได้รับ เป็นต้น ในกรณีที่ใช้ชิ้นส่วนที่มีค่าความคลาดเคลื่อน ที่กำหนดไว้ อุปกรณ์จะต้องได้รับการออกแบบให้ทำงานได้อย่างถูกต้องภายใต้สภาวะที่เลวร้ายที่สุดของค่าความคลาดเคลื่อนและสภาพแวดล้อมภายนอก
ประสิทธิภาพที่ดีที่สุดสำหรับอัลกอริทึม
ในวิทยาการคอมพิวเตอร์ คำว่า"ประสิทธิภาพในกรณีที่ดีที่สุด"ใช้เพื่ออธิบายพฤติกรรมของอัลกอริทึมภายใต้เงื่อนไขที่เหมาะสมที่สุด ตัวอย่างเช่น กรณีที่ดีที่สุดสำหรับการค้นหาเชิงเส้นอย่างง่ายในรายการเกิดขึ้นเมื่อองค์ประกอบที่ต้องการเป็นองค์ประกอบแรกของรายการ
การพัฒนาและการเลือกอัลกอริทึมนั้นแทบจะไม่ขึ้นอยู่กับประสิทธิภาพในกรณีที่ดีที่สุด: องค์กรทางวิชาการและเชิงพาณิชย์ส่วนใหญ่สนใจที่จะปรับปรุงความซับซ้อนในกรณีเฉลี่ยและ ประสิทธิภาพในกรณีที่เลวร้ายที่สุดมากกว่า อัลกอริทึมอาจได้รับการแก้ไขอย่างง่ายดายเพื่อให้มีเวลาทำงานในกรณีที่ดีที่สุดที่ดีโดยการเขียนโค้ดแบบตายตัวสำหรับชุดอินพุตที่จำกัด ทำให้การวัดแทบจะไม่มีความหมาย[ 2 ]
ผลการดำเนินงานกรณีเลวร้ายที่สุด เทียบกับผลการดำเนินงานแบบเฉลี่ย เทียบกับผลการดำเนินงานกรณีปกติ
การวิเคราะห์ประสิทธิภาพในกรณีที่เลวร้ายที่สุดและการวิเคราะห์ประสิทธิภาพในกรณีเฉลี่ยมีความคล้ายคลึงกันอยู่บ้าง แต่ในทางปฏิบัติมักต้องใช้เครื่องมือและวิธีการที่แตกต่างกัน
การกำหนด ความหมายของ อินพุตทั่วไปเป็นเรื่องยาก และบ่อยครั้งที่อินพุตโดยเฉลี่ยมีคุณสมบัติที่ทำให้ยากต่อการกำหนดลักษณะทางคณิตศาสตร์ (ลองพิจารณาอัลกอริทึมที่ออกแบบมาเพื่อใช้งานกับสตริงข้อความ) ในทำนองเดียวกัน แม้ว่าจะสามารถอธิบาย "กรณีเฉลี่ย" ที่เฉพาะเจาะจงได้ (ซึ่งอาจใช้ได้กับการใช้งานอัลกอริทึมบางอย่างเท่านั้น) แต่ก็มักจะส่งผลให้การวิเคราะห์สมการยากขึ้น[ 3 ]
การวิเคราะห์กรณีที่เลวร้ายที่สุดให้ ผลการวิเคราะห์ ที่ปลอดภัย (ไม่ควรประมาทกรณีที่เลวร้ายที่สุด) แต่ก็อาจมองโลกในแง่ร้าย เกินไปได้ เนื่องจากอาจไม่มีข้อมูลป้อนเข้า (ที่เป็นไปได้จริง) ที่จะต้องใช้ขั้นตอนมากขนาดนี้
ในบางสถานการณ์ อาจจำเป็นต้องใช้การวิเคราะห์ในแง่ร้ายเพื่อรับประกันความปลอดภัย อย่างไรก็ตาม บ่อยครั้ง การวิเคราะห์ในแง่ร้ายอาจมองโลกในแง่ร้ายเกินไป ดังนั้น การวิเคราะห์ที่เข้าใกล้ค่าจริงมากขึ้น แต่ในแง่ดี (อาจมีโอกาสล้มเหลวต่ำที่ทราบ) อาจเป็นแนวทางที่ใช้งานได้จริงมากกว่า แนวทางสมัยใหม่ในทฤษฎีทางวิชาการเพื่อเชื่อมช่องว่างระหว่างการวิเคราะห์กรณีที่เลวร้ายที่สุดและการวิเคราะห์กรณีเฉลี่ย เรียกว่าการวิเคราะห์แบบปรับเรียบ (smoothed analysis )
ในการวิเคราะห์อัลกอริธึมที่มักใช้เวลาในการทำงานไม่นาน แต่บางครั้งอาจใช้เวลานานกว่ามากการวิเคราะห์แบบคิดค่าเสื่อมราคา (Amortized Analysis ) สามารถใช้เพื่อกำหนดเวลาการทำงานที่เลวร้ายที่สุดในช่วงการดำเนินการ (ซึ่งอาจไม่มีที่สิ้นสุด) ค่าใช้จ่ายแบบคิดค่า เสื่อมราคานี้จะใกล้เคียงกับค่าใช้จ่ายเฉลี่ยมากขึ้น ในขณะเดียวกันก็ยังรับประกันขีดจำกัดสูงสุดของเวลาการทำงาน ดังนั้นอัลกอริธึมแบบออนไลน์จึงมักใช้การวิเคราะห์แบบคิดค่าเสื่อมราคาเป็นพื้นฐาน
การวิเคราะห์กรณีที่เลวร้ายที่สุดเกี่ยวข้องกับความซับซ้อนของกรณีที่เลวร้ายที่สุด[ 4 ]
ผลกระทบในทางปฏิบัติ
อัลกอริทึมหลายตัวที่มีประสิทธิภาพแย่ในกรณีเลวร้ายที่สุด แต่มีประสิทธิภาพดีในกรณีเฉลี่ย สำหรับปัญหาที่เราต้องการแก้ไข นี่เป็นสิ่งที่ดี เพราะเราสามารถหวังได้ว่ากรณีเฉพาะที่เราสนใจจะเป็นกรณีเฉลี่ย แต่สำหรับด้านการเข้ารหัสลับนี่เป็นสิ่งที่ไม่ดีอย่างยิ่ง เพราะเราต้องการให้กรณีทั่วไปของปัญหาการเข้ารหัสลับนั้นยาก วิธีการต่างๆ เช่นการลดรูปตัวเองแบบสุ่มสามารถนำมาใช้กับปัญหาเฉพาะบางอย่างเพื่อแสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดไม่ได้ยากกว่ากรณีเฉลี่ย หรือในทางกลับกัน กรณีเฉลี่ยไม่ได้ง่ายกว่ากรณีที่เลวร้ายที่สุด
ในทางกลับกัน โครงสร้างข้อมูลบางอย่าง เช่นตารางแฮชมีพฤติกรรมในกรณีที่เลวร้ายที่สุดที่ไม่ดีนัก แต่ตารางแฮชที่เขียนอย่างดีและมีขนาดใหญ่พอ จะไม่มีทางเกิดกรณีที่เลวร้ายที่สุดขึ้นได้ในทางสถิติ เนื่องจากจำนวนการดำเนินการโดยเฉลี่ยจะลดลงตามเส้นโค้งแบบเลขชี้กำลัง ดังนั้นเวลาในการทำงานของการดำเนินการจึงมีขอบเขตจำกัดในทางสถิติ
ตัวอย่าง
อัลกอริทึมการเรียงลำดับ
| อัลกอริทึม | โครงสร้างข้อมูล | ความซับซ้อนของเวลา: ดีที่สุด | ความซับซ้อนด้านเวลา: ปานกลาง | ความซับซ้อนด้านเวลา: แย่ที่สุด | ความซับซ้อนของพื้นที่: แย่ที่สุด |
|---|---|---|---|---|---|
| เรียงลำดับอย่างรวดเร็ว | อาร์เรย์ | O( n log( n )) | O( n log( n )) | O( n 2 ) | บน) |
| การเรียงลำดับแบบผสาน | อาร์เรย์ | O( n log( n )) | O( n log( n )) | O( n log( n )) | บน) |
| การเรียงลำดับแบบฮีป | อาร์เรย์ | O( n log( n )) | O( n log( n )) | O( n log( n )) | O(1) |
| เรียงลำดับอย่างราบรื่น | อาร์เรย์ | บน) | O( n log( n )) | O( n log( n )) | O(1) |
| การเรียงลำดับแบบฟอง | อาร์เรย์ | บน) | O( n 2 ) | O( n 2 ) | O(1) |
| การเรียงลำดับแบบแทรก | อาร์เรย์ | บน) | O( n 2 ) | O( n 2 ) | O(1) |
| การเรียงลำดับแบบเลือก | อาร์เรย์ | O( n 2 ) | O( n 2 ) | O( n 2 ) | O(1) |
| จัดเรียงโบโก | อาร์เรย์ | บน) | O( n n !) | โอ(∞) | O(1) |
- การเรียงลำดับแบบแทรก (Insertion sort)ถูกนำมาใช้กับรายการที่มี องค์ประกอบ nตัว โดยสมมติว่าองค์ประกอบทั้งหมดแตกต่างกันและอยู่ในลำดับแบบสุ่มในตอนเริ่มต้น โดยเฉลี่ยแล้ว ครึ่งหนึ่งขององค์ประกอบในรายการA 1 ... A jจะมีค่าน้อยกว่าองค์ประกอบA j +1และอีกครึ่งหนึ่งจะมีค่ามากกว่า ดังนั้น อัลกอริทึมจะเปรียบเทียบองค์ประกอบที่ ( j + 1) ที่จะถูกแทรกโดยเฉลี่ยกับครึ่งหนึ่งของรายการย่อยที่เรียงลำดับแล้ว ดังนั้นt j = j /2 การคำนวณเวลาการทำงานโดยเฉลี่ยจะได้ฟังก์ชันกำลังสองของขนาดข้อมูลเข้า เช่นเดียวกับเวลาการทำงานในกรณีที่เลวร้ายที่สุด
- อัลกอริทึม QuickSortถูกนำมาใช้กับรายการที่มี องค์ประกอบ nตัว โดยสมมติว่าองค์ประกอบทั้งหมดแตกต่างกันและอยู่ในลำดับแบบสุ่มในตอนเริ่มต้นอัลกอริทึมการเรียงลำดับยอด นิยมนี้ มีประสิทธิภาพโดยเฉลี่ยอยู่ที่ O( n log( n ) ) ซึ่งทำให้เป็นอัลกอริทึมที่เร็วมากในทางปฏิบัติ แต่หากได้รับอินพุตที่แย่ที่สุด ประสิทธิภาพจะลดลงเหลือ O( n² ) นอกจากนี้ เมื่อนำไปใช้กับนโยบาย "เรียงจากสั้นที่สุดก่อน" ความซับซ้อนของพื้นที่ในกรณีที่แย่ที่สุดจะถูกจำกัดด้วย O(log( n )) แทน
- อัลกอริทึม Heapsort ใช้เวลา O(n) เมื่อองค์ประกอบทั้งหมดเหมือนกัน อัลกอริทึม Heapify ใช้เวลา O(n) และการลบองค์ประกอบออกจากฮีปใช้เวลา O(1) สำหรับแต่ละองค์ประกอบจำนวน n ตัว เวลาในการทำงานจะเพิ่มขึ้นเป็น O(nlog(n)) หากองค์ประกอบทั้งหมดต้องแตกต่างกัน
- Bogosortมีเวลาประมวลผล O(n) เมื่อเรียงลำดับองค์ประกอบในรอบแรก ในแต่ละรอบจะตรวจสอบว่าองค์ประกอบทั้งหมดอยู่ในลำดับที่ถูกต้องหรือไม่ มีการเรียงสับเปลี่ยนที่เป็นไปได้ n! แบบ ด้วยตัวสร้างเลขสุ่มแบบสมดุล เกือบทุกการเรียงสับเปลี่ยนของอาร์เรย์จะถูกสร้างขึ้นใน n! รอบ คอมพิวเตอร์มีหน่วยความจำจำกัด ดังนั้นตัวเลขที่สร้างขึ้นจึงวนซ้ำ อาจไม่สามารถเข้าถึงการเรียงสับเปลี่ยนทุกแบบได้ ในกรณีที่เลวร้ายที่สุด จะใช้เวลาประมวลผล O(∞) ซึ่งเป็นลูปอนันต์
โครงสร้างข้อมูล
| โครงสร้างข้อมูล | ความซับซ้อนเชิงเวลา | ความซับซ้อนของพื้นที่ | |||||||
|---|---|---|---|---|---|---|---|---|---|
| ค่าเฉลี่ย: การจัดทำดัชนี | เฉลี่ย: การค้นหา | เฉลี่ย: การแทรก | ค่าเฉลี่ย: การลบ | แย่ที่สุด: การจัดทำดัชนี | แย่ที่สุด: การค้นหา | แย่ที่สุด: การสอดใส่ | แย่ที่สุด: การลบ | แย่ที่สุด | |
| อาร์เรย์พื้นฐาน | O(1) | บน) | บน) | บน) | O(1) | บน) | บน) | บน) | บน) |
| อาร์เรย์ไดนามิก | O(1) | บน) | บน) | — | O(1) | บน) | บน) | — | บน) |
| ซ้อนกัน | บน) | บน) | O(1) | O(1) | บน) | บน) | O(1) | O(1) | บน) |
| คิว | บน) | บน) | O(1) | O(1) | บน) | บน) | O(1) | O(1) | บน) |
| รายการเชื่อมโยงเดี่ยว | บน) | บน) | O(1) | O(1) | บน) | บน) | O(1) | O(1) | บน) |
| รายการเชื่อมโยงสองทาง | บน) | บน) | O(1) | O(1) | บน) | บน) | O(1) | O(1) | บน) |
| รายการข้าม | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) | บน) | บน) | บน) | O( n log ( n )) |
| ตารางแฮช | — | O(1) | O(1) | O(1) | — | บน) | บน) | บน) | บน) |
| ต้นไม้ค้นหาแบบไบนารี | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) | บน) | บน) | บน) | บน) |
| ต้นไม้คาร์ทีเซียน | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | — | บน) | บน) | บน) | บน) |
| บี-ทรี | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) |
| ต้นไม้สีแดงดำ | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) |
| ต้นไม้แผ่กว้าง | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) |
| ต้นไม้ AVL | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) |
| ต้นไม้ Kd | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | บน) | บน) | บน) | บน) | บน) |
- การค้นหาเชิงเส้นในรายการที่มีnองค์ประกอบ ในกรณีที่เลวร้ายที่สุด การค้นหาจะต้องเข้าถึงทุกองค์ประกอบหนึ่งครั้ง ซึ่งเกิดขึ้นเมื่อค่าที่กำลังค้นหาเป็นองค์ประกอบสุดท้ายในรายการ หรือไม่มีอยู่ในรายการ อย่างไรก็ตาม โดยเฉลี่ยแล้ว สมมติว่าค่าที่ค้นหาอยู่ในรายการ และแต่ละองค์ประกอบในรายการมีโอกาสเท่ากันที่จะเป็นค่าที่ค้นหา การค้นหาจะเข้าถึงเพียงn /2 องค์ประกอบ เท่านั้น
ดูเพิ่มเติม
- อัลกอริทึมการเรียงลำดับ – เป็นสาขาที่มีการวิเคราะห์ประสิทธิภาพของอัลกอริทึมต่างๆ มากมาย
- โครงสร้างข้อมูลสำหรับการค้นหา – โครงสร้างข้อมูลใดๆ ที่ช่วยให้สามารถดึงข้อมูลรายการที่ต้องการได้อย่างมีประสิทธิภาพ
- การวิเคราะห์วงจรในกรณีที่เลวร้ายที่สุด
- การวิเคราะห์แบบปรับเรียบ
- องค์ประกอบไฟไนต์ช่วง
- สัญกรณ์บิ๊กโอ
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ กรณีที่ดีที่สุด กรณีที่แย่ที่สุด และกรณีเฉลี่ย
ใน วิทยาการคอมพิวเตอร์ กรณี ที่ดีที่สุด แย่ ที่สุด และ เฉลี่ย ของ อัลกอริทึม ที่กำหนด แสดงถึงการใช้ ทรัพยากร อย่างน้อยที่สุด มาก ที่สุด และ โดย เฉลี่ย ตามลำดับ...
ผลการดำเนินงานกรณีเลวร้ายที่สุด เทียบกับผลการดำเนินงานแบบเฉลี่ย เทียบกับผลการดำเนินงานกรณีปกติ
การวิเคราะห์ประสิทธิภาพในกรณีที่เลวร้ายที่สุดและการวิเคราะห์ประสิทธิภาพในกรณีเฉลี่ยมีความคล้ายคลึงกันอยู่บ้าง แต่ในทางปฏิบัติมักต้องใช้เครื่องมือและวิธีการที่แตกต่างกัน
ผลกระทบในทางปฏิบัติ
อัลกอริทึมหลายตัวที่มีประสิทธิภาพแย่ในกรณีเลวร้ายที่สุด แต่มีประสิทธิภาพดีในกรณีเฉลี่ย สำหรับปัญหาที่เราต้องการแก้ไข นี่เป็นสิ่งที่ดี เพราะเราสามารถหวังได้ว่ากรณีเฉพาะที่เราสนใจจะเป็นกรณีเฉลี่ย แต่สำหรับด้าน การเข้ารหัสลับ นี่เป็นสิ่งที่ไม่ดีอย่างยิ่ง...
อัลกอริทึมการเรียงลำดับ
อัลกอริทึม โครงสร้างข้อมูล ความซับซ้อนของเวลา: ดีที่สุด ความซับซ้อนด้านเวลา: ปานกลาง ความซับซ้อนด้านเวลา: แย่ที่สุด ความซับซ้อนของพื้นที่: แย่ที่สุด เรียงลำดับอย่างรวดเร็ว อาร์เรย์ O( n log( n )) O( n log( n )) O( n 2 ) บน ) การเรียงลำดับแบบผสาน อาร์เรย์ O(...