Ký hiệu Big-O: độ phức tạp thời gian

Tối ưu hóa mã trong Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Độ phức tạp thời gian là gì?

Độ phức tạp thời gian: Đo mức tăng thời gian chạy theo kích thước đầu vào
Giúp trả lời: "Điều gì xảy ra khi dữ liệu lớn hơn 10×?"
Không tập trung vào thời gian tuyệt đối

Ký hiệu Big-O

Ký hiệu toán học mô tả kịch bản xấu nhất.

Một số lớp độ phức tạp phổ biến:

O(1): Thời gian hằng - không phụ thuộc kích thước

Hiểu O(1)

Ví dụ thao tác O(1) là get() của ArrayList

Cài đặt nội bộ (đơn giản) cho ArrayList chứa String:

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)
    }
}

Ký hiệu Big-O

Ký hiệu toán học mô tả kịch bản xấu nhất

Một số lớp độ phức tạp phổ biến:

O(1): Thời gian hằng - không phụ thuộc kích thước
O(n): Thời gian tuyến tính - tăng theo kích thước đầu vào

Hiểu O(n)

Ví dụ tương tự cho contains() của 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
}

Ký hiệu Big-O

Ký hiệu toán học mô tả kịch bản xấu nhất

Một số lớp độ phức tạp phổ biến:

O(1): Thời gian hằng - không phụ thuộc kích thước
O(n): Thời gian tuyến tính - tăng theo kích thước đầu vào
O(n²): Thời gian bậc hai - tăng theo bình phương kích thước

Ví dụ thực tế với độ phức tạp bậc hai

// 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!")
            }
        }
    }
}

Vì sao độ phức tạp thời gian quan trọng

Ảnh hưởng của kích thước đầu vào:

O(1): 1.000 -> 1.000.000 mục = Thời gian như nhau!
O(n): 1.000 -> 1.000.000 mục = Chậm hơn 1.000×
O(n²): 1.000 -> 1.000.000 mục = Chậm hơn 1.000.000×

Ảnh chụp màn hình 10-05-2025 lúc 2:27:06 CH.png

Ayo berlatih!

Tối ưu hóa mã trong Java