Big-O notation: ความซับซ้อนด้านเวลา

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

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

ความซับซ้อนด้านเวลาคืออะไร?

ความซับซ้อนด้านเวลา: วัดว่าเวลาทำงานเพิ่มขึ้นอย่างไรตามขนาด input
ตอบคำถามว่า: "จะเกิดอะไรขึ้นถ้าข้อมูลเพิ่มขึ้น 10 เท่า?"
ไม่ได้เน้นที่เวลาจริงในหน่วยวินาที

Big-O notation

สัญกรณ์ทางคณิตศาสตร์สำหรับอธิบายกรณีเลวร้ายที่สุด

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

O(1): เวลาคงที่ — ไม่ขึ้นกับขนาด

ทำความเข้าใจ O(1)

ตัวอย่างของ O(1) คือ get() ของ ArrayList

การ implement ภายใน (แบบย่อ) ของ ArrayList ที่เก็บ Strings:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Big-O notation

สัญกรณ์ทางคณิตศาสตร์สำหรับอธิบายกรณีเลวร้ายที่สุด

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

O(1): เวลาคงที่ — ไม่ขึ้นกับขนาด
O(n): เวลาเชิงเส้น — เพิ่มตามขนาด input

ทำความเข้าใจ O(n)

ตัวอย่างคล้ายกัน แต่เป็น contains() ของ ArrayList

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Big-O notation

สัญกรณ์ทางคณิตศาสตร์สำหรับอธิบายกรณีเลวร้ายที่สุด

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

O(1): เวลาคงที่ — ไม่ขึ้นกับขนาด
O(n): เวลาเชิงเส้น — เพิ่มตามขนาด input
O(n²): เวลากำลังสอง — เพิ่มแบบ quadratic ตามขนาด input

ตัวอย่างจริงของความซับซ้อนแบบ quadratic

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

ทำไมความซับซ้อนด้านเวลาจึงสำคัญ

ผลกระทบของขนาด input:

O(1): 1,000 -> 1,000,000 รายการ = ใช้เวลาเท่าเดิม!
O(n): 1,000 -> 1,000,000 รายการ = ช้าลง 1,000 เท่า
O(n²): 1,000 -> 1,000,000 รายการ = ช้าลง 1,000,000 เท่า

กราฟเปรียบเทียบความซับซ้อนของ Big-O

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

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