แนวคิดการเพิ่มขนาดอาร์เรย์แบบไดนามิก
เมื่อสร้างอาร์เรย์ด้วยการจัดสรรหน่วยความจำแบบไดนามิก (Dynamic Memory Allocation) สามารถเพิ่มขนาดอาร์เรย์เป็นสองเท่าได้โดยทำตามขั้นตอนบางขั้นตอน
ตัวอย่าง
อาร์เรย์เริ่มต้นขนาด 5:
| 0 | 1 | 2 | 3 | 4 |
| Element 1 | Element 2 | Element 3 | Element 4 | Element 5 |
หลังเพิ่มขนาดเป็นสองเท่า (ขนาด 10):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Element 1 | Element 2 | Element 3 | Element 4 | Element 5 | Element 6 | Element 7 | Element 8 | Element 9 | Element 10 |
ขั้นตอนการทำงาน
- สร้างอาร์เรย์ใหม่ขนาด m
- คัดลอก n องค์ประกอบจากอาร์เรย์เก่าไปอาร์เรย์ใหม่
- เปลี่ยนตัวชี้อาร์เรย์เดิมให้ชี้ไปอาร์เรย์ใหม่
การวิเคราะห์ความซับซ้อน (Complexity Analysis)
- การสร้างอาร์เรย์ขนาด m ใช้เวลา θ(m) เนื่องจากต้อง initialize ค่าเริ่มต้น
- การคัดลอก n องค์ประกอบใช้เวลา θ(n)
- รวมเป็น θ(m + n) โดยปกติ m = 2n ดังนั้น θ(3n) ≈ θ(n)
แม้การดำเนินการนี้จะ "มีค่าใช้จ่ายสูง" (Expensive) แต่ถ้ากระจายค่าใช้จ่าย (Amortized) ตลอด n การดำเนินการต่อเนื่อง จะเพิ่มเพียง θ(1) ต่อการดำเนินการหนึ่งครั้ง สรุปคือ การเพิ่มขนาดอาร์เรย์ด้วยตัวคูณคงที่ ไม่ส่งผลเสียต่อความซับซ้อนเชิง渐近 (Asymptotic Complexity)
