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

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 07:48, 4 กันยายน 2552 โดย Aoy (คุย | มีส่วนร่วม) (→‎ข้อย่อย 2)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

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

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

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

ข้อย่อย 1

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

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

ข้อย่อย 2

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

ส่วนเวลาการทำงาน สามารถคิดได้ดังนี้ ในการรวมอะเรย์ที่มีขนาด เข้าด้วยกันให้เป็นอะเรย์ที่มีขนาด นั้น แต่ละคู่จะใช้เวลา ซึ่งมีทั้งหมด คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น ส่วนชั้นที่สองที่เป็นการรวมอะเรย์ที่มีขนาด เข้าเป็นอะเรย์ที่มีขนาด นั้น แต่ละคู่จะใช้เวลา ซึ่งมีทั้งหมด คู่ ดังนั้นเวลาการทำงานทั้งหมดของ tree ชั้นนี้จะเป็น คิดแบบนี้ไปเรื่อย ๆ ก็จะได้เวลาการทำงานของแต่ละชั้นเป็น ซึ่ง tree มีทั้งหมด ชั้น ดังนั้นเวลาการทำงานทั้งหมด ก็จะเป็น

MergeLog.JPG