Kompleksitas Waktu dan Memori

Sebelum memilih algoritma atau struktur data untuk masalah tertentu, kita perlu cara yang konsisten untuk mengukur kinerjanya. Kompleksitas waktu dan kompleksitas memori adalah dua dimensi utama yang dipakai untuk membandingkan algoritma. Pada chapter ini kita akan mengukur jumlah operasi konkret dari beberapa algoritma untuk berbagai ukuran input, lalu membandingkan dua pendekatan klasik: solusi hemat waktu tetapi boros memori (menggunakan hash map) versus solusi hemat memori tetapi lambat. Pembaca akan melihat bahwa trade-off antara waktu dan ruang adalah keputusan desain yang lazim dalam pemrograman.

Apa Itu Kompleksitas #

Kompleksitas waktu mengukur bagaimana jumlah operasi tumbuh seiring ukuran input n. Kompleksitas memori mengukur bagaimana jumlah memori tambahan yang dibutuhkan tumbuh seiring n. Keduanya dinyatakan dalam notasi Big-O yang akan kita bedah tuntas pada chapter berikutnya.

Untuk sekarang, kita akan mengukur jumlah operasi konkret: berapa kali loop dieksekusi untuk n = 10, 100, 1000, 10000. Pendekatan ini memperlihatkan dengan jelas bagaimana algoritma O(n), O(n²), dan O(log n) berperilaku berbeda saat n membesar.

Mengukur Jumlah Operasi #

// Demo Kompleksitas Waktu dan Memori: ukur jumlah operasi vs ukuran input.

fun jumlahOperasiLoop(n: Int): Int {
    var hitung = 0
    for (i in 1..n) hitung++
    return hitung
}

fun jumlahOperasiNested(n: Int): Int {
    var hitung = 0
    for (i in 1..n) {
        for (j in 1..n) hitung++
    }
    return hitung
}

fun jumlahOperasiLog(n: Int): Int {
    var hitung = 0
    var i = n
    while (i > 1) {
        i /= 2
        hitung++
    }
    return hitung
}

// Contoh trade-off time vs space: hitung frekuensi elemen
// Pendekatan 1: O(n) time, O(1) space
fun frekuensiTarget(arr: IntArray, target: Int): Int {
    var hitung = 0
    for (x in arr) {
        if (x == target) hitung++
    }
    return hitung
}

// Pendekatan 2: O(n) time, O(n) space (hash map)
fun frekuensiSemua(arr: IntArray): Map<Int, Int> {
    val map = mutableMapOf<Int, Int>()
    for (x in arr) map[x] = (map[x] ?: 0) + 1
    return map
}

fun main() {
    println("=== Demo Kompleksitas Waktu dan Memori ===")

    val ukuran = listOf(10, 100, 1000, 10000)
    println("Jumlah operasi untuk berbagai ukuran input:")
    println("%-10s %-12s %-12s %-12s".format("n", "O(n)", "O(n^2)", "O(log n)"))
    for (n in ukuran) {
        val linier = jumlahOperasiLoop(n)
        val nested = jumlahOperasiNested(n)
        val log = jumlahOperasiLog(n)
        println("%-10d %-12d %-12d %-12d".format(n, linier, nested, log))
    }

    println()
    println("--- Trade-off time vs space ---")
    val data = intArrayOf(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)
    val target = 5
    println("Data: ${data.toList()}")
    println("Frekuensi $target (O(n) time, O(1) space): ${frekuensiTarget(data, target)}")

    val map = frekuensiSemua(data)
    println("Frekuensi semua (O(n) time, O(n) space): $map")

    println()
    println("--- Memori yang dialokasikan ---")
    println("Array of ${data.size} Int = ${data.size * 4} bytes (4 byte per Int)")
    println("HashMap dengan ${map.size} entry ~= ${map.size * 32} bytes (estimasi)")
}

Output yang Dihasilkan:

=== Demo Kompleksitas Waktu dan Memori ===
Jumlah operasi untuk berbagai ukuran input:
n          O(n)         O(n^2)       O(log n)    
10         10           100          3           
100        100          10000        6           
1000       1000         1000000      9           
10000      10000        100000000    13          

--- Trade-off time vs space ---
Data: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
Frekuensi 5 (O(n) time, O(1) space): 3
Frekuensi semua (O(n) time, O(n) space): {3=2, 1=2, 4=1, 5=3, 9=1, 2=1, 6=1}

--- Memori yang dialokasikan ---
Array of 11 Int = 44 bytes (4 byte per Int)
HashMap dengan 7 entry ~= 224 bytes (estimasi)

Bedah Kode Baris-per-Baris #

Mari kita amati baris-baris kunci:

1. Baris 3-7 (jumlahOperasiLoop): Loop for berjalan n kali. Kompleksitas waktu O(n); kompleksitas memori O(1) karena hanya memakai satu variabel hitung.
2. Baris 9-14 (jumlahOperasiNested): Loop bersarang; loop dalam berjalan n kali untuk setiap iterasi loop luar, total n × n = n² operasi. Kompleksitas O(n²).
3. Baris 16-23 (jumlahOperasiLog): Variabel i dibagi dua setiap iterasi. Jumlah iterasi kira-kira log₂(n). Kompleksitas O(log n), tumbuh sangat lambat bahkan untuk n besar.
4. Baris 27-33 (frekuensiTarget): Mencari satu target dengan loop tunggal. Kompleksitas waktu O(n), memori O(1). Cocok bila kita hanya butuh frekuensi satu nilai.
5. Baris 36-40 (frekuensiSemua): Membangun hash map dari semua elemen. Kompleksitas waktu O(n), memori O(n) karena map menyimpan setiap elemen unik. Memberi akses cepat ke frekuensi semua nilai dalam O(1) per lookup.

Trade-off Waktu vs Memori #

Pilihan tergantung pola penggunaan. Bila kita hanya mencari satu nilai, loop tunggal cukup. Bila kita akan query banyak nilai, hash map jauh lebih efisien walaupun memakan memori lebih besar.

Memori yang Sering Diabaikan #

Memori bukan sekadar ukuran data. Setiap object di JVM memiliki overhead header (12-16 byte), reference 4-8 byte, dan padding. Sebuah ArrayList<Int> dengan 1000 elemen bisa memakan lebih dari 4000 byte karena auto-boxing setiap Int menjadi Integer. Untuk data numerik besar, IntArray (4 byte per elemen, tanpa boxing) jauh lebih efisien.

Penutup #

Kompleksitas waktu dan memori adalah dua lensa utama untuk menilai algoritma. Pemilihan algoritma selalu melibatkan trade-off antara waktu dan ruang; jarang ada solusi yang menang di kedua dimensi. Pada chapter berikutnya kita akan membedah Big-O Notation secara formal, mulai dari O(1) hingga O(2ⁿ).

Referensi #

• Kotlin Coding Conventions
• Big-O Cheat Sheet

Referensi Lanjutan #

• Kotlin Collections overview — pengantar resmi koleksi Kotlin sebagai rujukan kompleksitas operasi List, Set, dan Map