Kompleksitas algoritma adalah ukuran seberapa banyak operasi yang dibutuhkan sebuah kode ketika ukuran datanya bertambah. Bukan seberapa cepat CPU kamu, bukan seberapa mahal servernya. Kode yang butuh 1 juta operasi akan selalu kalah dari kode yang butuh 1 operasi, mau dijalankan di laptop kentang atau server sultan. Dan yang menentukan jumlah operasi itu, sebagian besar, adalah pilihan struktur data.

Ini bagian kedua dari seri Belajar Struktur Data dari Nol. Di artikel ini kita buktikan klaim di atas lewat eksperimen langsung: mencari satu item di antara 1 juta data dengan dua cara berbeda, lalu mengukur selisihnya. Setelah itu kita belajar cara mengukur yang benar pakai micro-benchmark bawaan Go.

Prasyarat Sebelum Mulai

Kamu butuh Go yang sudah terpasang dan paham cara menjalankan file Go sederhana. Kalau belum, ikuti dulu bagian pertama: Belajar Struktur Data dari Nol: Pengenalan dan Persiapan Go. Semua kode di artikel ini saya uji dengan Go 1.23.1 di Linux, tapi jalan normal di Go 1.21 ke atas. Cek versi kamu dengan go version.

Eksperimen: Mencari 1 Item di Antara 1 Juta Data

Kita mulai dari eksperimen, bukan teori. Buat folder baru, lalu jalankan dua perintah ini:

mkdir kompleksitas && cd kompleksitas
go mod init kompleksitas

Buat file main.go berisi kode berikut. Kode ini menyiapkan 1 juta ID user, lalu mencari satu ID yang sama dengan dua cara: loop satu per satu di slice, dan akses langsung di map.

package main

import (
	"fmt"
	"time"
)

func main() {
	const n = 1_000_000
	target := "user-999999"

	// Siapkan data: 1 juta ID di slice dan di map
	daftar := make([]string, 0, n)
	indeks := make(map[string]bool, n)
	for i := 0; i < n; i++ {
		id := fmt.Sprintf("user-%d", i)
		daftar = append(daftar, id)
		indeks[id] = true
	}

	// Cara 1: loop seluruh slice
	mulai := time.Now()
	ketemu := false
	for _, id := range daftar {
		if id == target {
			ketemu = true
			break
		}
	}
	fmt.Println("slice:", ketemu, "butuh", time.Since(mulai))

	// Cara 2: akses langsung ke map
	mulai = time.Now()
	_, ada := indeks[target]
	fmt.Println("map  :", ada, "butuh", time.Since(mulai))
}

Jalankan dengan go run main.go. Di laptop yang saya pakai, hasilnya kira-kira seperti ini:

slice: true butuh 13.003519ms
map  : true butuh 819ns

Angka di mesin kamu pasti berbeda, tapi polanya akan sama: map menang telak. Di contoh ini selisihnya ribuan kali lipat. Padahal dua-duanya menjawab pertanyaan yang sama persis: apakah user-999999 ada di dalam data.

Kenapa Selisihnya Sejauh Itu: Jumlah Operasi, Bukan Kecepatan CPU

Loop di slice memeriksa item satu per satu dari depan. Target kita ada di posisi terakhir, jadi Go harus melakukan sekitar 1 juta perbandingan string sebelum ketemu. Map bekerja beda: dia menghitung hash dari kata kunci, lalu langsung melompat ke lokasi penyimpanannya. Berapa pun jumlah datanya, operasinya tetap segelintir.

Di sinilah inti kompleksitas algoritma. Yang kita hitung bukan detik, tapi jumlah operasi sebagai fungsi dari ukuran data. Perhatikan tabel ini:

Jumlah data	Perkiraan operasi loop slice (kasus terburuk)	Perkiraan operasi akses map
1.000	1.000	sekitar 1
1.000.000	1.000.000	sekitar 1
1.000.000.000	1.000.000.000	sekitar 1

CPU yang dua kali lebih cepat cuma memotong waktu jadi setengah. Tapi mengganti slice ke map memotong 1 miliar operasi jadi satu. Tidak ada upgrade hardware yang bisa menyaingi itu. Makanya programmer berpengalaman lebih dulu bertanya “struktur datanya apa” sebelum bertanya “servernya apa”.

Time Complexity vs Space Complexity

Kompleksitas algoritma punya dua sisi yang selalu tarik-menarik:

Time complexity: berapa banyak operasi yang dibutuhkan seiring data membesar. Ini yang barusan kita lihat di eksperimen.
Space complexity: berapa banyak memori tambahan yang dipakai seiring data membesar.

Eksperimen kita sebenarnya contoh klasik dari tarik-menarik ini. Map kita cepat karena dia menyimpan struktur tambahan di memori: bucket, hash, dan metadata lain. Kita membayar memori ekstra untuk membeli kecepatan. Loop slice hemat memori karena tidak butuh struktur tambahan apa pun, tapi bayarannya waktu.

Tidak ada jawaban yang selalu benar. Kalau datanya cuma 20 item dan dicari sekali, loop slice sudah lebih dari cukup. Kalau datanya jutaan dan dicari ribuan kali per detik, struktur tambahan seperti map jadi wajib. Kemampuan menimbang ini yang akan terus kita asah sepanjang seri.

Praktik: Menulis Micro-Benchmark dengan testing.B

Mengukur pakai time.Since cocok untuk demo, tapi kurang bisa diandalkan untuk keputusan serius. Sekali jalan bisa kena gangguan: sistem operasi lagi sibuk, cache CPU masih dingin, atau garbage collector kebetulan aktif. Go menyediakan alat resmi untuk ini: benchmark di package testing.

Buat file cari.go berisi dua fungsi yang mau kita adu:

package main

func CariDiSlice(data []string, target string) bool {
	for _, v := range data {
		if v == target {
			return true
		}
	}
	return false
}

func CariDiMap(data map[string]bool, target string) bool {
	return data[target]
}

Lalu buat file cari_test.go. Nama file wajib berakhiran _test.go dan nama fungsi wajib diawali Benchmark:

package main

import (
	"fmt"
	"testing"
)

const jumlahData = 100_000

// Variabel global sebagai penampung hasil,
// supaya compiler tidak menghapus kode yang diukur.
var hasil bool

func siapkanSlice() []string {
	data := make([]string, 0, jumlahData)
	for i := 0; i < jumlahData; i++ {
		data = append(data, fmt.Sprintf("user-%d", i))
	}
	return data
}

func siapkanMap() map[string]bool {
	data := make(map[string]bool, jumlahData)
	for i := 0; i < jumlahData; i++ {
		data[fmt.Sprintf("user-%d", i)] = true
	}
	return data
}

func BenchmarkCariDiSlice(b *testing.B) {
	data := siapkanSlice()
	target := "user-99999"
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		hasil = CariDiSlice(data, target)
	}
}

func BenchmarkCariDiMap(b *testing.B) {
	data := siapkanMap()
	target := "user-99999"
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		hasil = CariDiMap(data, target)
	}
}

Dua detail penting di kode ini. Pertama, b.ResetTimer() dipanggil setelah data disiapkan, supaya waktu menyiapkan 100 ribu item tidak ikut terhitung. Kedua, hasil fungsi disimpan ke variabel global hasil, alasannya kita bahas di bagian troubleshooting. Jalankan dengan:

go test -bench=. -benchmem

Contoh keluaran di mesin saya:

goos: linux
goarch: amd64
pkg: kompleksitas
cpu: Intel(R) Core(TM) i5-10310U CPU @ 1.70GHz
BenchmarkCariDiSlice-8        2326    537460 ns/op       0 B/op       0 allocs/op
BenchmarkCariDiMap-8      86166330     22.97 ns/op       0 B/op       0 allocs/op
PASS
ok      kompleksitas    4.353s

Cara Membaca Hasil Benchmark Go

Angka setelah nama fungsi (3021 dan 29847216) adalah b.N, yaitu berapa kali Go mengulang pengukuran. Go sendiri yang menentukan jumlah ini sampai hasilnya stabil secara statistik. Inilah bedanya dengan time.Since yang cuma mengukur sekali.
ns/op adalah rata-rata nanodetik per operasi. Di sini pencarian slice makan sekitar 537 ribu nanodetik, pencarian map sekitar 23 nanodetik.
B/op dan allocs/op muncul karena flag -benchmem, menunjukkan alokasi memori per operasi. Ini sisi space complexity dalam angka nyata.

Kasus Nyata di Backend: Full Scan vs Lookup Terindeks

Pola slice vs map ini bukan cuma soal latihan. Ini persis pola yang muncul di database. Query yang menyaring kolom tanpa indeks memaksa database membaca seluruh tabel baris per baris, istilahnya full table scan. Sama seperti loop slice kita. Query di kolom yang terindeks bisa melompat langsung ke baris yang dicari, sama seperti akses map.

Tim Arrazy beberapa kali menemukan kasus ini saat membangun sistem aplikasi untuk klien: endpoint yang terasa cepat saat data masih ratusan mendadak lambat setelah data tumbuh ke ratusan ribu. Kodenya tidak berubah sama sekali. Yang berubah cuma ukuran datanya, dan kompleksitas yang tadinya tidak terasa mulai menagih. Solusinya hampir selalu sama polanya: ganti cara akses dari scan menyeluruh ke lookup terindeks, entah lewat indeks database, map di memori, atau cache.

Pelajaran praktisnya: kode yang lolos testing dengan data kecil belum tentu selamat di produksi. Kompleksitas baru kelihatan giginya saat data membesar.

Troubleshooting: Error yang Sering Dialami Pemula Saat Benchmark

Benchmark terlihat mustahil cepat, misalnya 0.25 ns/op

Penyebab: hasil fungsi tidak dipakai, jadi compiler Go menganggap kodenya percuma dan menghapusnya. Yang kamu ukur akhirnya loop kosong. Ini disebut dead code elimination, dan hasilnya benchmark bohong. Solusi: simpan hasil ke variabel global seperti hasil di contoh kita, atau pakai b.Loop() di Go 1.24 ke atas yang otomatis mencegah optimasi ini. Kalau kamu melihat angka di bawah 1 ns/op untuk operasi yang jelas berat, curigai masalah ini.

go test tidak menjalankan benchmark sama sekali

Penyebab paling umum ada dua. Pertama, menjalankan go test tanpa flag -bench, karena secara default Go hanya menjalankan fungsi Test, bukan Benchmark. Kedua, salah tulis pola, misalnya -bench tanpa nilai akan error flag needs an argument. Solusi: selalu sertakan pola, minimal -bench=. yang artinya jalankan semua benchmark.

Muncul pesan “no test files”

Penyebab: nama file tidak berakhiran _test.go, atau file test beda package dengan kode yang diuji. Solusi: pastikan nama file persis berpola nama_test.go dan baris package di file test sama dengan file utamanya.

Angka hasil benchmark berubah-ubah tiap kali dijalankan

Penyebab: mesin kamu mengerjakan hal lain saat benchmark jalan, misalnya browser dengan banyak tab atau proses build lain. Variasi 5 sampai 10 persen itu normal. Solusi: tutup aplikasi berat, lalu jalankan beberapa putaran dengan go test -bench=. -count=5 dan bandingkan hasilnya. Keputusan diambil dari pola beberapa putaran, bukan dari satu angka keramat.

Latihan: Prediksi Dulu, Baru Buktikan

Kebiasaan paling berharga dari bagian ini: sebelum menjalankan benchmark, tulis dulu prediksimu. Cocokkan setelahnya. Coba tiga latihan ini:

Ubah target di benchmark menjadi "user-0", item paling depan. Prediksi dulu: apakah BenchmarkCariDiSlice jadi jauh lebih cepat, sama saja, atau lebih lambat? Bagaimana dengan map? Jalankan dan cocokkan.
Ubah jumlahData dari 100.000 menjadi 1.000.000. Prediksi: waktu slice naik sekitar 10 kali lipat atau tetap? Waktu map bagaimana? Buktikan.
Cari target yang tidak ada di data, misalnya "tidak-ada". Prediksi mana yang paling terpengaruh, lalu jalankan.

Kalau prediksimu meleset, justru bagus. Di situ letak belajarnya: cari tahu kenapa angka nyata tidak sesuai bayanganmu. Latihan nomor 1 misalnya, sering mengejutkan pemula karena slice mendadak menang.

Lanjut ke Bagian Berikutnya

Kamu sekarang sudah merasakan sendiri bahwa jumlah operasi menentukan performa, dan sudah bisa mengukurnya dengan benar pakai benchmark. Yang belum kita punya adalah bahasa standar untuk menyebut perbedaan itu. Menyebut “sekitar 1 juta operasi” tiap kali jelas tidak praktis.

Bahasa standar itu namanya notasi Big O, dan itu bahasan bagian ketiga: Big O Notation: Cara Mengukur Kompleksitas Algoritma. Artikelnya terbit menyusul, pantau daftar lengkapnya di halaman hub Belajar Struktur Data dari Nol.

Kompleksitas Algoritma: Kenapa Struktur Data Menentukan Performa