Notasi Big O dan Kompleksitas Waktu Algoritma

Notasi Big O adalah cara menyatakan kompleksitas waktu algoritma, yaitu seberapa cepat banyak langkah bertambah ketika ukuran masukan $n$ membesar. Misalnya, pencarian linear berkompleksitas $O(n)$, sedangkan binary search $O(\log n)$. Big O tidak mengukur detik, melainkan pola pertumbuhan, dan biasanya dipakai untuk kasus terburuk.

Apa Itu Kompleksitas Waktu?

Waktu eksekusi dalam detik bergantung pada komputer, bahasa, dan beban sistem. Agar perbandingan adil, kita menghitung banyak operasi dasar, misalnya perbandingan atau penjumlahan, sebagai fungsi dari ukuran masukan $n$. Hasilnya disebut kompleksitas waktu. Analisis serupa untuk pemakaian memori disebut kompleksitas ruang.

Yang penting bukan angka pastinya, tetapi bagaimana angka itu tumbuh. Algoritma $O(n)$ yang datanya dilipatduakan kira-kira membutuhkan dua kali langkah; algoritma $O(n^2)$ membutuhkan empat kali langkah.

Kelas Kompleksitas yang Paling Sering Muncul

Notasi	Nama	Contoh	$n = 10$	$n = 1.000$
$O(1)$	konstan	akses data[i]	1	1
$O(\log n)$	logaritmik	binary search	≈ 3	≈ 10
$O(n)$	linear	pencarian linear, sum(data)	10	1.000
$O(n \log n)$	linearitmik	sorted(data), merge sort	≈ 33	≈ 10.000
$O(n^2)$	kuadratik	dua loop bersarang	100	1.000.000
$O(2^n)$	eksponensial	mencoba semua himpunan bagian	1.024	≈ $10^{301}$

Kolom angka menunjukkan perkiraan banyak langkah. Perhatikan bagaimana $O(n^2)$ dan $O(2^n)$ meledak ketika $n$ membesar.

Cara Menghitung Big O dari Kode Python

1. Tentukan apa itu $n$, misalnya panjang list.
2. Satu perulangan sepanjang $n$ menyumbang $O(n)$.
3. Perulangan bersarang dikalikan: $n \times n = O(n^2)$.
4. Bagian kode yang berurutan dijumlahkan: $O(n) + O(n) = O(2n)$.
5. Sederhanakan hasilnya.

Contoh Soal Big O dan Pembahasan

Contoh 1: O(1) dan O(n)

def pertama(data):
    return data[0]

def jumlah(data):
    total = 0
    for x in data:
        total += x
    return total

pertama hanya melakukan satu akses, berapa pun panjang list, sehingga $O(1)$. jumlah mengunjungi setiap elemen sekali, sehingga $O(n)$.

Contoh 2: O(n²) dengan loop bersarang

def ada_duplikat_lambat(data):
    n = len(data)
    for i in range(n):
        for j in range(i + 1, n):
            if data[i] == data[j]:
                return True
    return False

Pada kasus terburuk (tidak ada duplikat), banyak perbandingan adalah $\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$, sehingga kompleksitasnya $O(n^2)$.

Contoh 3: Memperbaiki menjadi O(n) dengan set

def ada_duplikat_cepat(data):
    terlihat = set()
    for x in data:
        if x in terlihat:
            return True
        terlihat.add(x)
    return False

Pemeriksaan x in terlihat pada set rata-rata $O(1)$, sehingga seluruh fungsi rata-rata $O(n)$. Harganya adalah memori tambahan $O(n)$ untuk set: kita menukar ruang dengan waktu.

Contoh 4: Membuktikan pertumbuhan secara empiris

def hitung_perbandingan(n):
    langkah = 0
    for i in range(n):
        for j in range(i + 1, n):
            langkah += 1
    return langkah

for n in [10, 100, 1000]:
    print(n, hitung_perbandingan(n))

Keluarannya 10 45, 100 4950, dan 1000 499500. Saat $n$ dikali 10, banyak langkah kira-kira dikali 100, ciri khas $O(n^2)$.

Kasus Terbaik, Rata-rata, dan Terburuk

Pencarian linear yang menemukan target di elemen pertama hanya butuh 1 langkah (kasus terbaik), tetapi kasus terburuknya $n$ langkah. Karena itu kita biasa menyebut pencarian linear $O(n)$. Dalam analisis algoritma juga dikenal notasi $\Omega$ (Big Omega, batas bawah) dan $\Theta$ (Big Theta, batas atas sekaligus bawah).

Biaya Operasi Struktur Data Python

Operasi	Kompleksitas
data[i] pada list	$O(1)$
data.append(x)	$O(1)$ diamortisasi
data.insert(0, x)	$O(n)$
x in data pada list	$O(n)$
x in s pada set, d[k] pada dict	$O(1)$ rata-rata
sorted(data)	$O(n \log n)$

Kesalahan yang Sering Terjadi

Ringkasan

• Big O menyatakan batas atas pertumbuhan banyak langkah terhadap ukuran masukan $n$.
• Urutan umum: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$.
• Loop bersarang dikalikan, kode berurutan dijumlahkan, lalu buang konstanta dan suku kecil.
• Pilihan struktur data, seperti set dibanding list, dapat menurunkan kompleksitas.

Materi Terkait

Contoh nyata $O(n)$ dan $O(\log n)$ dibahas di pencarian linear dan biner. Biaya operasi list dan dictionary dijelaskan di list dan dictionary Python. Setelah membuat versi kode yang lebih cepat, pastikan hasilnya tetap benar dengan unit test Python.

def ada_duplikat_lambat(data):
    n = len(data)
    for i in range(n):
        for j in range(i + 1, n):
            if data[i] == data[j]:
                return True
    return False


def ada_duplikat_cepat(data):
    terlihat = set()
    for x in data:
        if x in terlihat:
            return True
        terlihat.add(x)
    return False


contoh = [4, 8, 15, 16, 23, 42, 8]
print(ada_duplikat_lambat(contoh), ada_duplikat_cepat(contoh))
print(ada_duplikat_lambat([1, 2, 3]), ada_duplikat_cepat([1, 2, 3]))

Sumber belajar

• Python Wiki: TimeComplexity
• MIT OpenCourseWare 6.0001: Lecture 12, Searching and Sorting
• Python Tutorial: Data Structures

Penjelasan dan contoh disusun ulang untuk materi ini; sumber dapat dibuka untuk belajar lebih lanjut.