ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบผสาน"

เก็บกวาดบทความด้วยบอต
ไม่มีความย่อการแก้ไข
(เก็บกวาดบทความด้วยบอต)
{{Infobox Algorithm
|class=[[ขั้นตอนวิธีการเรียงลำดับ]]
|image=[[Fileไฟล์:Merge-sort-example-300px300px.gif]]
|caption=ภาพตัวอย่างการเรียงลำดับแบบผสาน เร่ิมเร่มด้วยการแบ่งข้อมูลออกเป็นส่วนที่เล็กที่สุด แล้วเร่ิมเร่มผสานข้อมูลก้อนเล็ก ๆ เข้าด้วยกันกลายเป็นข้อมูลก้อนที่ใหญ่ขึ้น ในที่สุดข้อมูลทุกชิ้นจะเรียงลำดับอย่างสมบูรณ์
|data=[[แถวลำดับ]] (Array)
|time=O(''n'' log ''n'')
 
==การวิเคราะห์==
[[Imageไฟล์:merge sort algorithm diagram.svg|thumb|right|300px|ภาพแสดงการเรียงลำดับแถวลำดับ 7 ตัวด้วยวิธีการผสาน (แบบบนลงล่าง)]]
ในการเรียงลำดับข้อมูลทั้งสิ้น 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'') ดังที่ได้กล่าวไว้
 
417,867

การแก้ไข