Penjelasan notasi Big O dengan contoh

Masalah apa yang diselesaikan Big O

Mengukur waktu program dalam detik hanya menggambarkan satu mesin, satu bahasa, dan satu input. Big O menjawab pertanyaan yang lebih berguna: jika input menjadi 10 kali lebih besar, seberapa banyak pekerjaan tambahan yang dilakukan algoritma? Algoritma yang bekerja 10 kali lebih banyak berskala sangat berbeda dari yang bekerja 100 kali lebih banyak.

Secara formal, f(n) adalah O(g(n)) jika ada konstanta c dan n₀ sehingga f(n) ≤ c · g(n) untuk setiap n ≥ n₀. Dalam bahasa sederhana, g adalah batas atas pertumbuhan f ketika n sudah cukup besar, dengan mengabaikan faktor konstanta.

• n adalah ukuran input: panjang list, jumlah karakter dalam string, atau jumlah node dalam graf.
• Kompleksitas waktu menghitung langkah dasar (perbandingan, assignment, aritmetika).
• Kompleksitas ruang menghitung memori tambahan yang dipakai, tidak termasuk input itu sendiri.

Cara menyederhanakan ekspresi

Hitung jumlah langkah sebagai fungsi dari n, lalu terapkan dua aturan: buang faktor konstanta dan pertahankan hanya suku yang dominan.

Jika sebuah algoritma punya dua input yang independen, pertahankan keduanya: perulangan atas list sepanjang n lalu atas list sepanjang m adalah O(n + m), dan perulangan di dalam perulangan adalah O(n · m). Basis logaritma tidak berpengaruh dalam Big O, karena log₂ n dan log₁₀ n hanya berbeda oleh faktor konstanta.

Kelas kompleksitas yang umum

Sebagai patokan kasar: di komputer modern, perulangan sederhana bisa menjalankan puluhan juta langkah dasar per detik di Python dan jauh lebih banyak di bahasa yang dikompilasi. Jadi O(n log n) aman untuk jutaan item, O(n²) mulai lambat pada puluhan ribu item, dan O(2ⁿ) tidak realistis di atas sekitar 40 sampai 60 item.

Membaca kompleksitas dari kode Python

Perhatikan perulangannya. Satu perulangan atas input adalah O(n). Perulangan yang bersarang di dalam perulangan lain atas input yang sama adalah O(n²). Perulangan yang membagi dua rentang tersisa pada setiap langkah adalah O(log n).

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

Pemanggilan fungsi pustaka punya biaya sendiri. x in some_list adalah O(n), x in some_set adalah O(1) rata-rata, list.insert(0, x) adalah O(n) karena setiap elemen bergeser, dan sorted() adalah O(n log n). Perulangan yang memanggil operasi O(n) sebanyak n kali menjadi O(n²), meskipun tampak seperti satu perulangan biasa.

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

Kasus terbaik, rata-rata, dan terburuk

Algoritma yang sama bisa membutuhkan jumlah pekerjaan berbeda pada input berbeda dengan ukuran yang sama, sehingga kompleksitas sering dinyatakan untuk tiga kasus.

Jika orang hanya menyebut “kompleksitas X”, biasanya yang dimaksud adalah kasus terburuk, atau kasus rata-rata untuk hash table dan quicksort. Biaya teramortisasi (amortized) adalah ide keempat: menambah elemen ke list Python kadang O(n) ketika list memperbesar penyimpanannya, tetapi rata-rata O(1) pada banyak operasi append.

Big O, Big Omega, dan Big Theta

Secara ketat, algoritma O(n) juga merupakan O(n²), karena O hanyalah batas atas. Dalam praktik sehari-hari, orang menulis Big O tetapi maksudnya batas paling ketat yang mereka ketahui, yaitu yang dinyatakan oleh Θ.

Kesalahan umum

• Melupakan biaya operasi bawaan, seperti in pada list atau slicing items[1:], yang menyalin dan berbiaya O(k) untuk k elemen yang disalin.
• Salah menghitung pemanggilan rekursif: fungsi yang memanggil dirinya sendiri dua kali dengan n − 1 adalah O(2ⁿ), bukan O(n).
• Mengabaikan ruang: membuat list baru berukuran n, atau rekursi sedalam n, memakan memori O(n).
• Menulis O(2n) atau O(n + 5). Keduanya disederhanakan menjadi O(n).