418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 3

อินพุต: อะเรย์ที่เรียงแล้วจำนวน k อะเรย์ แต่ละอะเรย์มีสมาชิกอยู่ $n\,$ ตัว

เอาพุต: รวมอะเรย์ที่เป็นอินพุตให้เป็นอะเรย์ที่เรียงแล้วขนาด $kn\,$ ช่อง

วัตถุที่เราต้องตรวจสอบคือ สมาชิกแต่ละตัวในแต่ละอะเรย์ เงื่อนไขคือ อะเรย์สุดท้ายที่ใช้รวมต้องเรียงด้วย

ข้อย่อย 1

พิจารณาการรวมอะเรย์ดังต่อไปนี้

ขั้นตอนที่ 1 การรวมอะเรย์ที่เรียงแล้วขนาด $n\,$ ตัวที่หนึ่ง เข้ากับอะเรย์ที่เรียงแล้วขนาด$n\,$ ตัวที่สอง เวลาในการรวมจะเป็น $2n\,$

ขั้นตอนที่ 2 การรวมอะเรย์ที่เรียงแล้วขนาด $2n\,$ จากขั้นตอนที่ 1 เข้ากับอะเรย์ที่เรียงแล้วขนาด$n\,$ ตัวที่สาม เวลาในการรวมจะเป็น $3n\,$

ขั้นตอนที่ k-1 การรวมอะเรย์ที่เรียงแล้วขนาด $(k-1)n\,$ จากขั้นตอนที่ k-2 เข้ากับอะเรย์ที่เรียงแล้วขนาด$n\,$ ตัวที่ k เวลาในการรวมจะเป็น $kn\,$

ดังนั้นเวลารวมทั้งหมดจะเป็น $2n+3n+...+kn=O(nk^{2})\,$

ข้อย่อย 2

แนวคิดในการรวมจะรวมอะเรย์ทีละคู่ไปเรื่อย ๆ ตามรูป