บทที่ 22 divide and conquer
จบบทนี้ น้องจะแก้โจทย์ด้วยการแบ่งปัญหาเป็นครึ่ง แก้แต่ละครึ่ง แล้วรวมคำตอบ และอ่านเวลาที่ใช้ได้จากต้นไม้ของการแบ่ง จะเขียน merge sort กับ quicksort ได้เองพร้อมรู้ว่าแต่ละวิธีพังตอนไหน นับคู่สลับของข้อมูลสองแสนตัวได้ในเสี้ยววินาทีด้วยการนับระหว่างรวม หาอันดับที่ k ด้วย quickselect และ nth_element โดยไม่ต้องเรียงทั้งหมด และหาคู่จุดที่ใกล้ที่สุดบนระนาบ โจทย์ค่าย 2 และ TOI ที่ถามว่า "ต้องสลับกี่ครั้ง" "มีกี่คู่ที่ตัวหน้ามากกว่าตัวหลัง" หรือ "ตัวที่เล็กเป็นอันดับ k" ที่ N เป็นแสน ใช้ความรู้ในบทนี้โดยตรง
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 22.1 แบ่ง แก้ย่อย รวม | สามขั้นของ divide and conquer ต้นไม้การแบ่ง ทำไมลึกแค่ log N ชั้น decrease and conquer อย่าง binary search และยกกำลังเร็ว และตารางอ่านเวลาจากรูปของการแบ่ง |
| 22.2 merge sort | รวมสองแถวที่เรียงแล้ว เขียน merge sort พิสูจน์ O(N log N) ด้วยงานต่อชั้น วัดเวลาเทียบ insertion sort กับ sort และกับดักลืมเทส่วนที่เหลือกับจองอาเรย์พักทุกครั้ง |
| 22.3 นับคู่สลับด้วย merge sort | แบ่งคู่เป็นสามแบบ นับคู่ข้ามครึ่งระหว่างรวมด้วยบรรทัดเดียว นับเงื่อนไขอื่นด้วยตัวชี้ทางเดียว และกับดัก int กับ < |
| 22.4 quicksort และ quickselect | partition กรณีแย่ที่สุดกับข้อมูลที่เรียงแล้วที่วัดจริง สุ่มตัวแบ่ง ข้างในของ sort หาอันดับที่ k ด้วย quickselect และ nth_element และข้อมูลซ้ำเยอะ |
| 22.5 คู่จุดที่ใกล้ที่สุด | แบ่งระนาบด้วยเส้นตั้ง ดูเฉพาะแถบรอบเส้น ทำไมแต่ละจุดเทียบไม่เกิน 7 จุด และเวลาเทียบกับลองทุกคู่ |