Space Complexity คืออะไร?
Space Complexity (ความซับซ้อนของพื้นที่) หมายถึงปริมาณหน่วยความจำที่อัลกอริทึมใช้ (รวมถึงค่าอินพุตของอัลกอริทึม) เพื่อทำงานจนเสร็จและสร้างผลลัพธ์ออกมา
เราทราบว่าเพื่อให้อัลกอริทึมทำงาน ต้องโหลดลงในหน่วยความจำหลัก (Main Memory) หน่วยความจำสามารถใช้ในรูปแบบต่างๆ ได้ดังนี้:
- Variables (ตัวแปร): รวมถึงค่าคงที่และค่าชั่วคราว
- Program Instruction (คำสั่งโปรแกรม): โค้ดที่คอมไพล์แล้ว
- Execution (การทำงาน): พื้นที่สำหรับการดำเนินการระหว่างรัน
Auxiliary Space (พื้นที่ช่วยเหลือ)
Auxiliary Space คือพื้นที่เพิ่มเติมหรือพื้นที่ชั่วคราวที่อัลกอริทึมใช้ระหว่างการทำงาน (ไม่นับรวมพื้นที่ของอินพุต)
การใช้หน่วยความจำระหว่างการทำงานโปรแกรม
- Instruction Space: ใช้เก็บคำสั่งที่คอมไพล์แล้วในหน่วยความจำ
- Environmental Stack: ใช้เก็บที่อยู่เมื่อโมดูลหนึ่งเรียกอีกโมดูลหรือฟังก์ชันระหว่างการทำงาน
- Data Space: ใช้เก็บข้อมูล ตัวแปร และค่าคงที่ที่โปรแกรมจัดเก็บและอัปเดตระหว่างการทำงาน
