Notasi O

Latihan membuat instruksi pembelajaran untuk mengenal Notasi O atau Big-O Notation. Implementasi dalam bahasa pemrograman Rust.

Big-O Notation.

Notasi O atau Big-O Notation digunakan untuk menggambarkan seberapa cepat waktu eksekusi atau seberapa besar penggunaan memori dari sebuah algoritma bertambah saat ukuran data bertambah. Tujuannya bukan menghitung waktu persis, melainkan memberikan gambaran skala pertumbuhan.

Tujuan Pembelajaran

Setelah mempelajari materi ini, Anda akan mampu:

1. Menjelaskan arti Notasi O secara konseptual.

2. Mengidentifikasi kompleksitas umum seperti O(1), O(n), O(n²), dan O(log n).

3. Mengimplementasikan contoh kode Rust yang menggambarkan berbagai jenis kompleksitas.

4. Menjelaskan mengapa akses array adalah O(1) tetapi remove() di tengah array adalah O(n).

5. Mengenali edge case yang perlu diwaspadai dalam pengukuran kompleksitas.

Prasyarat

• Pemahaman dasar tentang array, loop for, dan operasi sederhana di Rust.

• Pemahaman bahwa program memerlukan waktu untuk dijalankan, dan waktu tersebut bisa berbeda jika data yang diproses lebih banyak.

Konsep Notasi O

Big-O menjelaskan laju pertumbuhan waktu eksekusi terhadap ukuran input (n).

• Tidak fokus pada angka detik atau milidetik.

• Mengabaikan detail kecil seperti konstanta atau optimasi minor.

• Membantu memilih algoritma yang tetap cepat meskipun data menjadi besar.

Contoh Jenis Kompleksitas dan Implementasi Rust

1. O(1) – Waktu Konstan

Operasi yang selalu memakan waktu sama, tidak peduli ukuran data.

fn main() {
    let data = [10, 20, 30, 40, 50];
    // Akses langsung indeks ke-2 selalu sama cepatnya
    println!("Elemen ke-2: {}", data[2]);
}

Penjelasan: Mengakses data[2] hanya melibatkan satu perhitungan alamat memori. Waktu tidak berubah walaupun array memiliki 5 atau 5 juta elemen.

2. O(n) – Waktu Linear

Waktu bertambah sebanding dengan jumlah data.

fn main() {
    let data = [10, 20, 30, 40, 50];
    let mut jumlah = 0;

    for x in data {
        jumlah += x; // Setiap elemen diproses satu per satu
    }

    println!("Jumlah semua elemen: {}", jumlah);
}

Penjelasan: Jika ada 5 elemen → 5 operasi. Jika ada 1.000 elemen → 1.000 operasi. Waktu bertambah linear terhadap n.

3. O(n²) – Waktu Kuadrat

Waktu bertambah sebanding dengan kuadrat dari jumlah data, biasanya karena nested loop.

fn main() {
    let data = [1, 2, 3, 4];

    for i in 0..data.len() {
        for j in 0..data.len() {
            println!("Pasangan: ({}, {})", data[i], data[j]);
        }
    }
}

Penjelasan: Jika ada n elemen, maka akan ada n × n pasangan. Jika n = 4, ada 16 iterasi. Jika n = 1000, ada 1.000.000 iterasi — sangat cepat membengkak.

4. O(log n) – Waktu Logaritmik

Biasanya terjadi jika data dibagi dua setiap langkah (misalnya pencarian biner).

fn binary_search(arr: &[i32], target: i32) -> bool {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = (left + right) / 2;
        if arr[mid] == target {
            return true;
        } else if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    false
}

fn main() {
    let data = [10, 20, 30, 40, 50];
    println!("Apakah ada 40? {}", binary_search(&data, 40));
}

Penjelasan: Setiap langkah membuang setengah data yang tidak relevan. Untuk 1.000.000 elemen, hanya butuh sekitar 20 langkah.

Mengapa Akses Array O(1) tetapi Remove O(n)?

Ketika Anda mengakses data[i], hanya ada satu perhitungan alamat memori → O(1).

Namun, ketika Anda menghapus elemen di tengah array:

1. Elemen tersebut dihapus.

2. Semua elemen setelahnya harus digeser satu per satu.

3. Jumlah pergeseran bergantung pada jumlah elemen setelah posisi yang dihapus.

Contoh Rust:

fn main() {
    let mut v = vec![10, 20, 30, 40, 50];
    println!("Sebelum: {:?}", v);

    v.remove(2); // Hapus indeks ke-2 (nilai 30)
    println!("Sesudah: {:?}", v);
}

Pada kasus ini, 40 dan 50 harus digeser ke kiri. Jika ada 1.000.000 elemen, maka bisa ada hampir 1.000.000 operasi geser → O(n).

Edge Case

• Array kosong: akses indeks akan panic di Rust. Pastikan selalu mengecek panjang array sebelum mengakses.

• Remove pada indeks terakhir: hanya menghapus elemen terakhir tanpa banyak geser, sehingga relatif lebih cepat.

• Insert di awal array: biaya tertinggi karena semua elemen harus digeser.

• Binary search: hanya valid jika array sudah terurut; jika tidak, hasilnya salah meskipun kodenya O(log n).

Refleksi

1. Mengapa kita perlu tahu kompleksitas algoritma bahkan sebelum menulis kode?

2. Jika sebuah operasi lambat untuk data yang besar, apakah ada alternatif algoritma yang lebih baik?

3. Dalam kasus nyata, kapan Anda harus memilih algoritma O(log n) dibanding O(n)?

4. Bagaimana Anda akan menguji kinerja program Anda untuk memastikan performa tetap baik saat data membesar?

5. Bagaimana Anda akan menjelaskan perbedaan O(1) dan O(n) kepada teman yang belum pernah belajar algoritma?

Memahami bagaimana membuat program yang efisien dengan mengerti Big-O Notation menjadi penting. Jika melihat kembali prasyarat untuk mengerti Notasi O ini cukup sederhana, di antaranya hanya array dan loop.

Untuk mempelajari array dan loop di pemrograman Rust bisa belajar di kelas Belajar Pemrograman Rust untuk Pemula di Dicoding.