Ký hiệu Big-O: độ phức tạp bộ nhớ

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

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Độ phức tạp bộ nhớ là gì?

Độ phức tạp thời gian mô tả kích thước đầu vào ảnh hưởng đến thời gian chạy
Độ phức tạp bộ nhớ mô tả kích thước đầu vào ảnh hưởng đến bộ nhớ sử dụng

Hiểu độ phức tạp bộ nhớ rất quan trọng để xây dựng ứng dụng:

Chỉ dùng lượng bộ nhớ cần thiết, không hơn
Tránh lỗi sập như OutOfMemoryError

Ký hiệu Big-O

Ký hiệu giống hệt độ phức tạp thời gian.

Một số lớp độ phức tạp thường gặp:

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

Phương thức tìm giá trị lớn nhất

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

Dù mảng số nguyên có 10 hay 10 triệu phần tử, ta chỉ dùng bộ nhớ cho một biến max
Độ phức tạp bộ nhớ là O(1) (không đổi)

Phương thức nhân đôi giá trị

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

Nếu đầu vào có n phần tử, cần thêm chỗ cho n phần tử
Độ phức tạp bộ nhớ là O(n) vì bộ nhớ tăng tuyến tính theo kích thước đầu vào

Phương thức tạo bảng cửu chương

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ếu n là 10, cần 100 ô; nếu n là 100, cần 10.000 ô
Phân loại là O(n²)

Vì sao độ phức tạp bộ nhớ quan trọng?

Bộ nhớ là tài nguyên hữu hạn!

Các ví dụ trước với đầu vào 10.000 phần tử:

findMax, O(1) -> chỉ thêm vài byte
doubleValues, O(n) -> khoảng 40KB bộ nhớ thêm
multiplicationTable, O(n²) -> khoảng 400MB bộ nhớ thêm

Biểu đồ cột cho thấy tăng 8 byte với findMax, 40KB với doubleValues, và 400MB với multiplicationTable

Độ phức tạp bộ nhớ vs. độ phức tạp thời gian

Đừng quên:

Đôi khi ta đổi bộ nhớ lấy thời gian
Đôi khi ta đổi thời gian lấy bộ nhớ
Lựa chọn đúng phụ thuộc vào ràng buộc cụ thể của bạn

Đồ họa minh họa đánh đổi giữa thời gian và bộ nhớ

Ayo berlatih!

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