Notasi Big-O: kompleksitas ruang

Optimasi Kode di Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Apa itu kompleksitas ruang?

Kompleksitas waktu menjelaskan bagaimana ukuran input memengaruhi runtime
Kompleksitas ruang menjelaskan bagaimana ukuran input memengaruhi penggunaan memori

Memahami kompleksitas ruang penting untuk membangun aplikasi yang:

Hanya memakai memori secukupnya
Menghindari crash seperti OutOfMemoryError

Notasi Big-O

Notasinya sama dengan kompleksitas waktu.

Beberapa kelas kompleksitas umum:

O(1): Konstan - tidak bergantung ukuran
O(n): Linear - tumbuh seiring ukuran input
O(n²): Kuadratik - tumbuh kuadratik terhadap ukuran input

Metode pencari maksimum

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

Baik array berisi 10 atau 10 juta elemen, kita hanya memakai memori untuk satu variabel max
Kompleksitas ruangnya O(1) atau konstan

Metode penggandaan

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

Jika input memiliki n elemen, kita butuh ruang untuk n elemen tambahan
Kompleksitas ruangnya O(n) karena memori ekstra tumbuh linear dengan ukuran input

Metode tabel perkalian

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

Jika n adalah 10, kita butuh 100 sel; jika n adalah 100, kita butuh 10.000 sel
Ini diklasifikasikan sebagai O(n²)

Mengapa kompleksitas ruang penting?

Memori itu terbatas!

Contoh sebelumnya untuk ukuran input 10.000 elemen:

findMax, O(1) -> hanya beberapa byte ekstra
doubleValues, O(n) -> sekitar 40KB memori ekstra
multiplicationTable, O(n²) -> sekitar 400MB memori ekstra

Plot batang yang menunjukkan kenaikan memori 8 byte untuk findMax, 40KB untuk doubleValues, dan 400MB untuk multiplicationTable

Kompleksitas ruang vs. waktu

Jangan lupa:

Kadang kita menukar ruang untuk waktu
Kadang kita menukar waktu untuk ruang
Pilihan yang tepat tergantung batasan Anda

Grafik yang melambangkan pertukaran antara waktu dan ruang

Ayo berlatih!

Optimasi Kode di Java