การค้นหาและการจัดเรียงแบบ Rekursion
แนะนำใหม่| English | ความหมาย |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | การแบ่งแยกและพิชิต |
| merge sort/mɜːdʒ sɔːt/ | การจัดเรียงแบบรวม |
| merge/mɜːdʒ/ | การรวม |
การเรียกซ้ำกับการค้นหาและการเรียงลำดับ
- หลักการ แบ่งแยกและพิชิต (divide-and-conquer) เดียวกันนี้คือพลังขับเคลื่อนของ การค้นหาแบบทวิภาค (binary search) แบบเรียกซ้ำและ การเรียงลำดับแบบรวม (merge sort) แบบเรียกซ้ำ.
- แบ่งปัญหาออกเป็นสองส่วน แก้ไขทั้งสองส่วน แล้วนำมารวมกัน.
- การค้นหาแบบทวิภาคแบบเรียกซ้ำ ค้นหาในครึ่งหนึ่งโดย เรียกตัวเอง เข้าไปในครึ่งนั้น.
- การเรียงลำดับแบบรวม เรียงลำดับแต่ละครึ่งก่อน แล้ว รวม ครึ่งที่เรียงลำดับแล้วเข้าด้วยกัน.
การค้นหาแบบทวิภาคแบบเรียกซ้ำ
- กรณีฐาน: ช่วงว่างหมายความว่า ไม่พบเป้าหมาย
- ดูที่ กึ่งกลาง ถ้าเป็นเป้าหมาย ให้กลับค่าดัชนี
- ถ้าเป้าหมายน้อยกว่า ให้ เรียกซ้ำในครึ่งซ้าย; มากกว่าให้ใช้ ครึ่งขวา
- แต่ละการเรียกจะลดช่วงข้อมูลลงครึ่งหนึ่ง — เป็น
O(log n)เดิมกัน แต่เขียนในรูปแบบ recursiveness
Merge sort
- แบ่งอาร์เรย์ออกเป็นสองครึ่ง; เรียงลำดับแต่ละครึ่งแบบเรียกซ้ำ
- กรณีพื้นฐาน: อาร์เรย์ที่มีขนาด 0 หรือ 1 ถือว่าเรียงลำดับเรียบร้อยแล้ว
- รวม: เวนทั้งสองครึ่งที่เรียงแล้ว โดยเลือกองค์ประกอบหน้าสุดที่น้อยกว่าเสมอ
- เร็วกว่าการจัดเรียง
n²มาก — ใช้งานประมาณn log n
ทำไม Divide-and-conquer ถึงชนะ
- การแบ่งปัญหาเหลือครึ่งหนึ่งในแต่ละขั้นตอน ทำให้เกิดตัวคูณ
log n - Merge sort ที่มี
n log nดีกว่า Selection/Insertion sort ที่มีn²ในอาร์เรย์ขนาดใหญ่ - กรณีฐาน (ว่างหรือมีองค์ประกอบเดียว) หยุดทุกกิ่งของต้นไม้เรียกซ้ำ
- มีรูปทรงเหมือนการเรียกซ้ำทั้งหมด: แบ่งลง แล้วรวมกลับขึ้น
Binary search แบบเรียกซ้ำเรียกซ้ำในครึ่งเดียว (เป้าหมายอยู่ในด้านใดด้านหนึ่ง); Merge sort เรียกซ้ำในทั้งสองครึ่งแล้วรวมเข้าด้วยกัน ทั้งคู่ต้องมีกรณีฐาน — ช่วงว่างหมายถึง "ไม่พบ" สำหรับ Binary search; อาร์เรย์ที่มี ⟨0⟩ หรือ ⟨1⟩ องค์ประกอบก็เรียงแล้วสำหรับ Merge sort Divide-and-conquer คือสิ่งที่ทำให้ทั้งสองวิธีนี้รวดเร็ว (O(log n) และ O(n log n))
การเรียงด้วย Merge-sort ⟨[3, 1, 2, 4]⟩:
- แบ่งเป็น ⟨
[3, 1]⟩ และ ⟨[2, 4]⟩; เรียงแต่ละส่วน → ⟨[1, 3]⟩ และ ⟨[2, 4]⟩ - รวม: เลือก ⟨1⟩, แล้ว ⟨2⟩, ต่อด้วย ⟨3⟩, แล้ว ⟨4⟩ → ⟨
[1, 2, 3, 4]⟩ - การรวมข้อมูลแต่ละครั้งจะเลือกองค์ประกอบหน้าสุดที่มีค่าน้อยกว่าเป็นลำดับ
การค้นหาแบบแบ่งครึ่งด้วยวิธี递归 (Recursive binary search) จะ recursion ไปที่ครึ่งใดครึ่งหนึ่ง (กรณีพื้นฐาน: ช่วงว่าง = ไม่พบ) สำหรับ O(log n) การค้นหา Merge sort จะ recursion ไปที่ทั้งสองครึ่งและ รวม เข้าด้วยกัน (กรณีพื้นฐาน: มี ⟨0 หรือ 1 ⟨元素) สำหรับ O(n log n) การเรียงลำดับ ทั้งสองเป็นแบบ divide-and-conquer: แยกออกแล้วรวมกลับขึ้นบน — เร็วกว่า n² มาก
Merge sort แบ่งเป็นสองส่วน, แล้วรวมกลับขึ้น
องค์ประกอบเดี่ยวถูกเรียงแล้ว (กรณีฐาน); การรวมจะเชื่อมโยง它們ขึ้นด้านบน
Binary search แบบ rekursion เรียกซ้ำกับ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เป้าหมายอยู่ที่ฝั่งหนึ่งของตรงกลางเท่านั้น
Merge sort เรียกซ้ำกับ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เรียงแต่ละครึ่ง, แล้วรวมสองส่วนที่เรียงแล้วเข้าด้วยกัน
กรณีฐานของ merge sort คือ数组ที่มี...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
หนึ่ง (หรือศูนย์) องค์ประกอบ ไม่จำเป็นต้องจัดเรียง
เวลาทำงานของ Merge sort ประมาณ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
log n ระดับของการแบ่ง, ทำงาน n ต่อระดับ
ทั้ง Binary search แบบ rekursion และ Merge sort เป็นอัลกอริทึม Divide-and-conquer
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ทั้งคู่แบ่งปัญหาออกเป็นสองส่วนและเรียกซ้ำ
เรียงลำดับขั้นตอนการรวมสำหรับครึ่ง [1,3] และ [2,4]
Difficulty 3/5 · 200 coins + a small bonus on first completion today
เลือกองค์ประกอบด้านหน้าที่น้อยกว่าเสมอ: 1, 2, 3, 4