ความซับซ้อนของการจัดเรียงแบบผสานคำนวณอย่างไร

2024 ผู้เขียน: Lynn Donovan | [email protected]. แก้ไขล่าสุด: 2023-12-15 23:54

2 คำตอบ การแยกโหนด A[L, R] ออกเป็นสองโหนดจะใช้เวลา R−L+1 ครั้งแล้ว การรวมตัว โหนดย่อยทั้งสอง A[L, M] และ A[M+1, R] ใช้เวลา A[R−L+1] อีกครั้ง ดังนั้นสำหรับทุกโหนด จำนวนการดำเนินการที่ อัลกอริทึม ดำเนินการเท่ากับสองเท่าของขนาดของอาร์เรย์ที่สอดคล้องกับโหนดนั้น

เกี่ยวกับเรื่องนี้ การเรียงลำดับการผสานทำงานอย่างไร

ต่อไปนี้คือวิธีที่การจัดเรียงแบบผสานใช้การหารและพิชิต:

1. หารด้วยการหาจำนวน q ของตำแหน่งตรงกลางระหว่าง p และ r
2. พิชิตด้วยการเรียงลำดับอาร์เรย์ย่อยซ้ำๆ ในแต่ละปัญหาย่อยสองปัญหาที่สร้างโดยขั้นตอนการหาร
3. รวมโดยการรวมอาร์เรย์ย่อยที่เรียงลำดับทั้งสองกลับเข้าไปในอาร์เรย์ย่อยที่เรียงลำดับเดียว[p..

นอกจากนี้ ความซับซ้อน O ขนาดใหญ่สำหรับการเรียงลำดับการผสานคืออะไร ผสานการเรียงลำดับ เป็นคอกม้า เรียงลำดับ ซึ่งหมายความว่าองค์ประกอบเดียวกันในอาร์เรย์จะรักษาตำแหน่งเดิมโดยสัมพันธ์กัน เวลาโดยรวม ความซับซ้อน ของ ผสานการเรียงลำดับ เป็น อู๋ (nLogn). มันมีประสิทธิภาพมากกว่าเนื่องจากในกรณีที่เลวร้ายที่สุดคือรันไทม์คือ อู๋ (nlogn) พื้นที่ ความซับซ้อน ของ ผสานการเรียงลำดับ เป็น อู๋ (NS).

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

n*log(n)

การเรียงลำดับการผสานทำการเปรียบเทียบได้มากเพียงใด

เมื่อเราหมดองค์ประกอบในรายการใดรายการหนึ่ง เราจะใส่องค์ประกอบที่เหลือลงในช่องสุดท้ายของ จัดเรียง รายการ. ผลที่ตามมา, การรวมตัว สองรายการที่มีองค์ประกอบทั้งหมด n รายการต้องมีมากที่สุด n-1 การเปรียบเทียบ.