ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบผสาน"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ลไม่มีความย่อการแก้ไข |
|||
บรรทัด 1:
{{Infobox Algorithm
|class=[[ขั้นตอนวิธีการเรียงลำดับ]]
|image=[[
|caption=ภาพตัวอย่างการเรียงลำดับแบบผสาน
|data=[[แถวลำดับ]] (Array)
|time=O(''n'' log ''n'')
บรรทัด 56:
==การวิเคราะห์==
[[
ในการเรียงลำดับข้อมูลทั้งสิ้น n ชุด ''การเรียงลำดับแบบผสาน'' มีประสิทธิภาพในกรณีดีที่สุด (โดยมิได้ใส่เงื่อนไขพิเศษ) กรณีเฉลี่ย และกรณีแย่สุด เท่ากันคือ O(''n'' log ''n'') โดยจะแสดงให้ดูดังนี้ สมมติให้เวลาที่ใช้ในการเรียงข้อมูล n ชุด แทนด้วย ''T''(''n'') เนื่องจาก ''การเรียงลำดับแบบผสาน'' มีสองขั้นตอนโดย'''ขั้นแรก'''คือการแบ่งเป็นสองส่วนซึ่งสามารถทำได้ในเวลาคงที่แต่จะต้องเวียงบังเกิดเรียกตัวเองลงไปแก้ปัญหาที่เล็กลงครึ่งหนื่งสองปัญหา จะได้ว่าในส่วนแรกใช้เวลา 2''T''(''n''/2) และ'''ขั้นที่สอง'''ซึ่งเป็นการผสานข้อมูลสองชุดที่เล็กกว่า (ที่เรียงในตัวเองแล้ว) เป็นข้อมูลชุดใหญ่จะใช้เวลาอีก ''n'' ดังที่ได้แสดงให้ดูในตัวอย่างการอิมพลิเมนต์ด้านบน เมื่อรวมทั้งสองขั้นแล้วจะใช้เวลาทั้งสิ้น ''T''(''n'') = 2''T''(''n''/2) + ''n'' หากใช้ [[Master Theroem]] ในการวิเคราะห์สมการนี้จะได้ผลลัพทธ์เป็น O(''n'' log ''n'') ดังที่ได้กล่าวไว้
| |||