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

แนวคิด จะทำคล้าย ๆ กับ merge sort ธรรมดา โดยการรวมจะรวมอะเรย์สองตัวที่มีขนาด $n\,$ เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด $2n\,$ หลังจากนั้น รวมอะเรย์ที่มีขนาด $2n\,$ เข้าเป็นอะเรย์ที่มีขนาด $4n\,$ ทำแบบนี้ไปเรื่อย ๆ จนได้อะเรย์ที่เรียงแล้ว และมีขนาดเป็น $kn\,$

ส่วนเวลาการทำงาน สามารถคิดได้ดังนี้ ในการรวมอะเรย์ที่มีขนาด $n\,$ เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด $2n\,$ นั้น แต่ละคู่จะใช้เวลา $2n=O(n)\,$ ซึ่งมีทั้งหมด $k/2\,$ คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น $(k/2)O(n)=O(kn)\,$ ส่วนชั้นที่สองที่เป็นการรวมอะเรย์ที่มีขนาด $2n\,$ เข้าเป็นอะเรย์ที่มีขนาด $4n\,$ นั้น แต่ละคู่จะใช้เวลา $4n=O(n)\,$ ซึ่งมีทั้งหมด $k/4\,$ คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น $(k/4)O(n)=O(kn)\,$ คิดแบบนี้ไปเรื่อย ๆ ก็จะได้เวลาการทำงานของแต่ละชั้นเป็น $O(nk)\,$ ซึ่ง tree มีทั้งหมด $\log k\,$ ชั้น ดังนั้นเวลาการทำงานทั้งหมด ก็จะเป็น $O(nk\log k)\,$