Belajar Algoritm - Randomized Algorithms

#Pendahuluan

Setelah di episode 23 kita membahas Geometric Algorithms, pada episode ini kita membahas Randomized Algorithms — algoritma yang menggunakan keacakan (random number) sebagai bagian dari logikanya. Randomized algorithms sering lebih sederhana, lebih cepat, atau lebih praktis dibandingkan deterministik counterpart-nya — dengan keyakinan probabilistik yang bisa dikontrol.

Randomized algorithms menjadi semakin relevan di era AI: approximate nearest neighbor (ANN) untuk vector search, randomized embeddings di LLM, dan Monte Carlo methods untuk inference. Memahami klasifikasi dan pola randomized memberikan fondasi untuk teknik modern ini.

#Klasifikasi: Las Vegas vs Monte Carlo

#Las Vegas

Las Vegas: selalu menghasilkan hasil yang benar, tetapi waktu eksekusi adalah random variable. Jika beruntung, sangat cepat; jika tidak, tetap benar tetapi lebih lambat.

Contoh: QuickSort dengan random pivot — selalu menghasilkan array terurut, tetapi waktu bervariasi. Rata-rata O(n log n), worst-case O(n²) tapi probability sangat kecil.

#Monte Carlo

Monte Carlo: waktu eksekusi tetap, tetapi hasilnya mungkin salah dengan probability kecil yang bisa dikontrol.

Contoh: Miller-Rabin primality test — menentukan apakah angka prima dengan probability error yang bisa diperkecil hingga 2^(-k) untuk k iterasi.

Aspek	Las Vegas	Monte Carlo
Hasil	Selalu benar	Mungkin salah (controlled)
Waktu	Random	Tetap
Trade-off	Waktu vs keberuntungan	Akurasi vs waktu
Contoh	QuickSort random pivot	Miller-Rabin

Note

Banyak randomized algorithms bisa dikonversi ke deterministik, tetapi dengan overhead yang signifikan. Randomized memberikan simplicity dan average-case performance yang sering lebih baik untuk praktik.

#QuickSelect: K-th Terkecil

QuickSelect menemukan k-th elemen terkecil dalam O(n) average — menggunakan partition seperti Quick Sort tetapi hanya mengeksplorasi satu sisi.

python

import random
 
def quickselect(arr, k):
    """K-th smallest element (0-indexed)"""
    if len(arr) == 1:
        return arr[0]
    
    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]
    
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

#Kompleksitas

Metrik	Nilai
Average	O(n)
Worst	O(n²) — sangat jarang dengan random pivot
Space	O(n) — bisa di-in-place

Alternatif deterministik: Median of medians → O(n) worst-case, tetapi dengan overhead konstanta yang tinggi. QuickSelect dengan random pivot lebih cepat di praktik.

#Randomized Hashing

Hash function yang baik mendistribusikan elemen secara merata. Tetapi ada adversarial input yang bisa membuat hash table menjadi O(n) — jika attacker tahu hash function-nya.

Randomized hashing menggunakan universal hash family: h(k) = ((a × k + b) mod p) mod m di mana a, b dipilih secara random. Ini menjamin expected O(1) untuk operasi apapun, tanpa batasan pada input.

python

class RandomHashTable:
    def __init__(self, capacity):
        self.p = 10**9 + 7  # prime large
        self.a = random.randint(1, self.p - 1)
        self.b = random.randint(0, self.p - 1)
        self.m = capacity
        self.table = [[] for _ in range(capacity)]
    
    def _hash(self, key):
        return ((self.a * hash(key) + self.b) % self.p) % self.m
    
    def put(self, key, value):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))
    
    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

#Skip List

Skip list adalah struktur data probabilistik yang menggantikan balanced BST (seperti AVL atau Red-Black Tree) dengan layered linked list yang di-random. Expected time untuk search, insert, delete: O(log n).

Ide: setiap node punya probabilitas p (biasanya 0.5) untuk "promoted" ke layer berikutnya. Layer 0 berisi semua elemen, layer 1 berisi ~50%, layer 2 ~25%, dan seterusnya.

plaintext

Layer 3:  1 ----------------------------→ 9
Layer 2:  1 ------→ 5 ------------------→ 9
Layer 1:  1 → 3 → 5 → 7 → 8 → 9
Layer 0:  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9

Skip list digunakan di Redis (sorted set) dan LevelDB sebagai alternatif balanced BST yang lebih sederhana.

Tip

Skip list menarik karena sederhana diimplementasikan (linked list dengan random promotion), tetapi memberikan O(log n) expected time — sama dengan balanced BST. Trade-off: tidak ada worst-case guarantee, tetapi probability pelanggaran sangat kecil.

#Penutup

Pada episode 24 ini, kalian telah memahami:

Las Vegas: selalu benar, waktu random — QuickSort random pivot, randomized QuickSelect.
Monte Carlo: waktu tetap, mungkin salah — Miller-Rabin, randomized hashing.
QuickSelect: O(n) average untuk k-th element — lebih cepat dari sorting.
Randomized hashing: universal hash family → expected O(1) tanpa adversarial attack.
Skip list: O(log n) expected untuk ordered operations — sederhana dan efisien.

Di episode 25 selanjutnya kita akan membahas Approximation & Online Algorithms — approximation ratios, vertex cover 2-approximation, dan ski rental problem. Sampai jumpa di episode 25!