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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 13: แถว 13:
  
 
== ข้อย่อย 2 ==
 
== ข้อย่อย 2 ==
 +
[[ไฟล์:mergeLog.JPG]]

รุ่นแก้ไขเมื่อ 09:30, 2 กันยายน 2552

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

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

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

ข้อย่อย 1

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

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

ข้อย่อย 2

MergeLog.JPG