[Review] A Practical Checklist for Algorithm Selection TODO
Concept
Algorithm choice isn't determined by asymptotic complexity alone — it depends on the combination of input size, data distribution, access pattern, memory hierarchy, update frequency, and worst-case versus average-case requirements. For example, when n is small, an O(n^2) algorithm with small constants beats O(n log n); when data is nearly sorted, an adaptive sort wins; and array-based structures with good cache locality often beat pointer-chasing structures in practice. If a workload is read-heavy, a static index is best; if write-heavy, a log-structured or amortization-friendly structure wins. If tail latency (p99) matters, avoid amortized algorithms that look good on average but are bad in the worst case. In the end, a checklist is a procedure: first identify which constraint dominates, then narrow to candidates that fit that constraint, and confirm with measurement.
Much of real-world performance trouble comes not from a wrong algorithm but from misidentifying the constraint, and that cost only shows up after the code has already hardened.
Code & Formula
# [복습] 알고리즘 선택 실전 기준표 — 입력 크기별 정렬 비용과 접근 패턴(배열 vs 연결리스트)의 실측 차이를 비교한다.
import time
import random
def insertion_sort(a):
a = a[:]
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
def timeit(fn, *args, repeat=1):
start = time.perf_counter()
for _ in range(repeat):
fn(*args)
return (time.perf_counter() - start) / repeat
random.seed(42)
small = [random.randint(0, 100) for _ in range(10)]
large = [random.randint(0, 100) for _ in range(2000)]
t_ins_small = timeit(insertion_sort, small, repeat=2000)
t_sorted_small = timeit(sorted, small, repeat=2000)
t_ins_large = timeit(insertion_sort, large, repeat=5)
t_sorted_large = timeit(sorted, large, repeat=5)
# 배열 순회(지역성 좋음) vs 연결 리스트류 포인터 추적(지역성 나쁨) 비교
class Node:
__slots__ = ("value", "next")
def __init__(self, value, next=None):
self.value = value
self.next = next
arr = list(range(100_000))
head = None
for v in reversed(arr):
head = Node(v, head)
def sum_linked(n):
total = 0
while n:
total += n.value
n = n.next
return total
t_array = timeit(sum, arr, repeat=20)
t_linked = timeit(sum_linked, head, repeat=20)
print(f"n=10: insertion_sort={t_ins_small * 1e6:.2f}us builtin(Timsort)={t_sorted_small * 1e6:.2f}us")
print(f"n=2000: insertion_sort={t_ins_large * 1e3:.2f}ms builtin(Timsort)={t_sorted_large * 1e3:.2f}ms")
print(f"n=100000 순회: array={t_array * 1e3:.3f}ms linked-list={t_linked * 1e3:.3f}ms "
f"(연결리스트가 {t_linked / t_array:.1f}배 — 캐시 지역성 차이)")
docs/code/algorithms/algorithms-19.py
Exercise
Pick a hot path you wrote recently, tabulate its input size, read/write ratio, and tail-latency requirements, then fill in the same columns for your current data structure and two alternatives to compare them on equal footing.
Practical Connection
On-chain code has one more axis because gas is a direct cost of complexity, while off-chain indexers and matching engines are often dominated by tail latency and update frequency.
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/.