ความซับซ้อนของกรณีที่เลวร้ายที่สุดของการเรียงลำดับฟองคืออะไร?

2024 ผู้เขียน: Fiona Howard | [email protected]. แก้ไขล่าสุด: 2024-01-10 06:43

Bubble sort บางครั้งเรียกว่า sinking sort เป็นอัลกอริธึมการจัดเรียงอย่างง่ายที่ทำตามขั้นตอนซ้ำ ๆ ในรายการ เปรียบเทียบองค์ประกอบที่อยู่ติดกันและสลับองค์ประกอบหากพวกเขาอยู่ในลำดับที่ไม่ถูกต้อง ผ่านรายการซ้ำจนกว่าจะเรียงลำดับรายการ

การเรียงลำดับความซับซ้อนในการเรียงลำดับฟองในกรณีที่เลวร้ายที่สุดคืออะไร

Bubble Sort เป็นอัลกอริธึมการจัดเรียงที่ใช้งานง่ายและเสถียรโดยมีความซับซ้อนด้านเวลา O(n²) ในกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุด – และ O(n) ใน ดีที่สุด

ทำไมกรณีที่แย่ที่สุดสำหรับการจัดเรียงฟองอากาศ N 2

กรณีที่แย่ที่สุดสำหรับการเรียงลำดับฟองสบู่คือ เมื่อองค์ประกอบที่เล็กที่สุดของรายการอยู่ที่ส่วนท้ายใหญ่ … ในกรณีที่เลวร้ายที่สุดนี้ มันต้องใช้การวนซ้ำ n ครั้งของการแลกเปลี่ยน n/2 ครั้ง ดังนั้นลำดับจึงเป็น อีกครั้ง n^2.

เหตุใดการจัดเรียงแบบฟองสบู่จึงแย่ที่สุด

สถานการณ์ที่เลวร้ายที่สุดสำหรับการเรียงลำดับแบบฟองสบู่คือ เมื่อองค์ประกอบที่เล็กที่สุดของรายการอยู่ในตำแหน่งสุดท้าย … ในสถานการณ์นี้ องค์ประกอบที่เล็กที่สุดจะเลื่อนลงมาหนึ่งตำแหน่งในแต่ละครั้งที่ผ่าน list หมายความว่าการเรียงลำดับจะต้องทำให้จำนวนรอบสูงสุดในรายการคือ n - 1.

คุณคำนวณความซับซ้อนของตัวพิมพ์ใหญ่ที่สุดของการเรียงลำดับแบบฟองได้อย่างไร

ในการคำนวณความซับซ้อนของอัลกอริธึมการจัดเรียงแบบฟอง จะเป็นประโยชน์ในการ กำหนดจำนวนการเปรียบเทียบที่แต่ละลูปดำเนินการ สำหรับแต่ละองค์ประกอบในอาร์เรย์ การเรียงลำดับแบบฟองจะทำการเปรียบเทียบ n -1 n-1 n-1 ในสัญกรณ์ O ใหญ่ การเรียงลำดับแบบฟองจะทำการเปรียบเทียบ O (n) O(n) O(n)