Online Algorithms and Competitive Ratio TODO
Concept
An online algorithm never gets to see the whole input in advance and has to make irrevocable decisions as each request arrives. Its performance is measured not in absolute cost but in competitive ratio, defined as the worst case over all input sequences of (online algorithm's cost) / (offline optimal's cost, knowing the whole input). For cache replacement (paging), with a cache of size k, both LRU and FIFO are k-competitive, and k is also the lower bound on the competitive ratio for any deterministic algorithm — which makes LRU optimal in that class. Allowing randomization, as in the marking algorithm, can lower the expected competitive ratio to logarithmic scale, because it prevents an adversarial input from predicting the algorithm's next move. Problems like ski rental, which are about deciding "when to buy," have a 2-competitive algorithm, and real-time selection problems in the secretary-problem family achieve constant-factor performance guarantees using randomized threshold rules.
Code that has to decide now, without knowing the future — caches, connection pools, real-time bidding, order matching — is everywhere, and average-case intuition alone falls apart under adversarial traffic. Competitive ratio is the one language that quantifies that worst case.
Code & Formula
# Day 15: 온라인 알고리즘과 경쟁비 — 캐시 교체(LRU/FIFO) 대 오프라인 최적(Belady)
# 미래를 모른 채 결정하는 온라인 알고리즘의 비용을 오프라인 최적과 비교해 경쟁비를 측정한다.
def lru_misses(seq, k):
cache, misses = [], 0
for x in seq:
if x in cache:
cache.remove(x); cache.append(x)
else:
misses += 1
if len(cache) >= k:
cache.pop(0)
cache.append(x)
return misses
def fifo_misses(seq, k):
cache, order, misses = set(), [], 0
for x in seq:
if x not in cache:
misses += 1
if len(cache) >= k:
oldest = order.pop(0)
cache.remove(oldest)
cache.add(x); order.append(x)
return misses
def belady_misses(seq, k):
cache, misses = [], 0
for i, x in enumerate(seq):
if x in cache:
continue
misses += 1
if len(cache) >= k:
future = seq[i + 1:]
farthest = max(cache, key=lambda c: future.index(c) if c in future else float("inf"))
cache.remove(farthest)
cache.append(x)
return misses
k = 4
seq = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] * 3 # LRU에 불리하도록 순환 접근 패턴
lru, fifo, opt = lru_misses(seq, k), fifo_misses(seq, k), belady_misses(seq, k)
print(f"캐시 크기 k={k}, 요청 {len(seq)}건")
print(f"LRU miss = {lru}, FIFO miss = {fifo}, 오프라인 최적(Belady) miss = {opt}")
print(f"LRU 경쟁비 ≈ {lru/opt:.2f} (이론 상한 k={k})")
print(f"FIFO 경쟁비 ≈ {fifo/opt:.2f}")
docs/code/algorithms/algorithms-15.py
Exercise
Implement LRU, FIFO, and random replacement under the same interface, then construct a cyclic access sequence sized to cache size k that's specifically designed to hit LRU's worst case, and measure whether the cost ratio against the offline optimum (Belady's algorithm) actually approaches k.
Practical Connection
A prediction-market order book that has to decide match-or-reject the instant each order arrives, or an RPC response cache exposed to an adversarial query pattern, are both exactly online decision problems.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.