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

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

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

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

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

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

ขั้นตอนที่ 1 การรวมอะเรย์ที่เรียงแล้วขนาด

n\,

ตัวที่หนึ่ง เข้ากับอะเรย์ที่เรียงแล้วขนาด

n\,

ตัวที่สอง เวลาในการรวมจะเป็น

2n\,

ขั้นตอนที่ 2 การรวมอะเรย์ที่เรียงแล้วขนาด

2n\,

จากขั้นตอนที่ 1 เข้ากับอะเรย์ที่เรียงแล้วขนาด

n\,

ตัวที่สาม เวลาในการรวมจะเป็น

3n\,

ขั้นตอนที่ k-1 การรวมอะเรย์ที่เรียงแล้วขนาด

(k-1)n\,

จากขั้นตอนที่ k-1 เข้ากับอะเรย์ที่เรียงแล้วขนาด

n\,

ตัวที่ k เวลาในการรวมจะเป็น

kn\,

ดังนั้นเวลารวมทั้งหมดจะเป็น

2n+3n+...+kn=O(nk^{2})\,

@@ แถว 6: / แถว 6: @@
 == ข้อย่อย 1===
+พิจารณาการรวมอะเรย์ดังต่อไปนี้
+:ขั้นตอนที่ 1 การรวมอะเรย์ที่เรียงแล้วขนาด <math> n \, </math> ตัวที่หนึ่ง เข้ากับอะเรย์ที่เรียงแล้วขนาด<math> n \,</math> ตัวที่สอง เวลาในการรวมจะเป็น <math> 2n \,</math>
+:ขั้นตอนที่ 2 การรวมอะเรย์ที่เรียงแล้วขนาด <math> 2n \, </math> จากขั้นตอนที่ 1 เข้ากับอะเรย์ที่เรียงแล้วขนาด<math> n \,</math> ตัวที่สาม เวลาในการรวมจะเป็น <math> 3n \,</math>
+:ขั้นตอนที่ k-1 การรวมอะเรย์ที่เรียงแล้วขนาด <math> (k-1)n \, </math> จากขั้นตอนที่ k-1 เข้ากับอะเรย์ที่เรียงแล้วขนาด<math> n \,</math> ตัวที่ k เวลาในการรวมจะเป็น <math> kn \,</math>
+:ดังนั้นเวลารวมทั้งหมดจะเป็น <math> 2n+3n+...+kn=O(nk^2) \,</math>
 == ข้อย่อย 2===