Big-O notation: space complexity

การปรับแต่งโค้ดใน Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Space complexity คืออะไร?

Time complexity อธิบายว่าขนาด input ส่งผลต่อ รันไทม์{{1}} อย่างไร
Space complexity อธิบายว่าขนาด input ส่งผลต่อ การใช้หน่วยความจำ{{2}} อย่างไร

การเข้าใจ space complexity มีความสำคัญในการสร้างแอปพลิเคชันที่:

ใช้หน่วยความจำเท่าที่จำเป็น ไม่มากเกินไป
ไม่ทำให้โปรแกรมหยุดทำงานด้วยข้อผิดพลาด เช่น OutOfMemoryError

Big-O Notation

รูปแบบสัญกรณ์เหมือนกับ time complexity

คลาสความซับซ้อนที่พบบ่อย:

O(1): Constant time — ไม่ขึ้นกับขนาด input
O(n): Linear time — เพิ่มตามขนาด input
O(n²): Quadratic time — เพิ่มแบบยกกำลังสองตามขนาด input

เมธอดหาค่าสูงสุด

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

ไม่ว่า array จะมี 10 หรือ 10 ล้านสมาชิก ใช้หน่วยความจำสำหรับตัวแปรเพียงตัวเดียวคือ max
Space complexity คือ O(1) หรือ constant space

เมธอดคูณสองค่า

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

หาก input มี n สมาชิก จะต้องการพื้นที่สำหรับสมาชิกเพิ่มอีก n ตัว
Space complexity คือ O(n) เนื่องจากหน่วยความจำที่ต้องการเพิ่มขึ้นเป็นเส้นตรงตามขนาด input

เมธอดสร้างตารางสูตรคูณ

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

ถ้า n เป็น 10 ต้องการ 100 ช่อง; ถ้า n เป็น 100 ต้องการ 10,000 ช่อง
จัดอยู่ใน complexity class O(n²)

Space complexity สำคัญอย่างไร?

หน่วยความจำเป็นทรัพยากรที่มีจำกัด!

ตัวอย่างก่อนหน้าเมื่อใช้งานจริง สำหรับ input ขนาด 10,000 สมาชิก:

findMax, O(1) -> ใช้หน่วยความจำเพิ่มเพียงไม่กี่ byte
doubleValues, O(n) -> ใช้หน่วยความจำเพิ่มประมาณ 40KB
multiplicationTable, O(n²) -> ใช้หน่วยความจำเพิ่มประมาณ 400MB

กราฟแท่งแสดงการเพิ่มขึ้นของหน่วยความจำ 8 byte สำหรับ findMax, 40KB สำหรับ doubleValues และ 400MB สำหรับ multiplicationTable

Space complexity vs. time complexity

อย่าลืมว่า:

บางครั้งเราแลก space เพื่อให้ได้ time ที่ดีขึ้น
บางครั้งเราแลก time เพื่อให้ได้ space ที่ดีขึ้น
การเลือกที่เหมาะสมขึ้นอยู่กับข้อจำกัดของแต่ละสถานการณ์

ภาพแสดงการแลกเปลี่ยนระหว่าง time และ space

มาฝึกกันเถอะ!

การปรับแต่งโค้ดใน Java