Notasi Big-O: kompleksitas waktu

Optimasi Kode di Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Apa itu kompleksitas waktu?

Kompleksitas waktu: Mengukur pertumbuhan runtime seiring ukuran input
Membantu menjawab: "Apa yang terjadi saat data 10× lebih besar?"
Tidak berfokus pada waktu absolut

Notasi Big-O

Notasi matematika untuk menggambarkan skenario terburuk.

Beberapa kelas kompleksitas umum:

O(1): Waktu konstan - tidak bergantung ukuran

Memahami O(1)

Contoh operasi O(1) adalah get() milik ArrayList

Implementasi internal (disederhanakan) untuk ArrayList yang menyimpan String:

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

    // Operasi get - akses array langsung
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Notasi Big-O

Notasi matematika untuk menggambarkan skenario terburuk

Beberapa kelas kompleksitas umum:

O(1): Waktu konstan - tidak bergantung ukuran
O(n): Waktu linear - naik seiring ukuran input

Memahami O(n)

Contoh serupa untuk contains() milik ArrayList

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

public int indexOf(Object o) {
    // Pencarian linear dalam array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Tidak ditemukan
}

Notasi Big-O

Notasi matematika untuk menggambarkan skenario terburuk

Beberapa kelas kompleksitas umum:

O(1): Waktu konstan - tidak bergantung ukuran
O(n): Waktu linear - naik seiring ukuran input
O(n²): Waktu kuadratik - naik kuadratik terhadap ukuran input

Contoh praktis dengan kompleksitas kuadratik

// Mencari pasangan angka yang jumlahnya sama dengan target
// Kompleksitas waktu: 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!")
            }
        }
    }
}

Mengapa kompleksitas waktu penting

Dampak ukuran input:

O(1): 1.000 -> 1.000.000 item = Waktu sama!
O(n): 1.000 -> 1.000.000 item = 1.000× lebih lambat
O(n²): 1.000 -> 1.000.000 item = 1.000.000× lebih lambat

Tangkapan layar 10 Mei 2025 pukul 14.27.06.png

Ayo berlatih!

Optimasi Kode di Java