Copy English

Why

A core algorithms-interview topic: proving that an operation with occasional expensive worst cases (like a dynamic array's resize-and-copy) is still O(1) on average over a sequence of operations, using the potential-function accounting method rather than a hand-wavy argument.

How it works

Planned: an interactive dynamic array (a growable vector) where each push is logged with its real cost, alongside a running potential function Φ that tracks "banked" cost from cheap operations — demonstrating that amortized cost = real cost + ΔΦ stays bounded even across a resize. Not yet built.

Where it lands in Jayverse

• Verex / Devnet: prove amortized cost with a potential function before assuming O(1). Any resizing structure (an order-book level array, an indexer's growable buffer) should get the Φ argument written down once, rather than assuming a resize-and-copy averages out.
• gitboard: log real cost per push alongside the running potential. That distinguishes a genuine O(n) regression in a growable per-market array from a normal, bounded amortized spike.

← All Knowledge Notes · Workspace Index · Top ↑

Copy 한국어

포텐셜 함수를 이용한 분할상환 분석

포텐셜 함수로 동적 배열 2배 증가의 분할상환 비용이 O(1)임을 증명.

알고리즘 — 2026-08-03 매일의 개발 지식 100 트랙 (Day 1/100).

왜

알고리즘 면접의 핵심 주제 중 하나입니다: 동적 배열의 resize-and-copy처럼 가끔 비싼 최악의 경우가 있는 연산이라도, 일련의 연산 전체로 보면 평균 O(1)임을 대충 넘어가는 논증이 아니라 포텐셜 함수 회계 기법으로 엄밀하게 증명합니다.

동작 방식

계획: 각 push 연산의 실제 비용을 기록하는 인터랙티브 동적 배열(확장 가능한 벡터)을 만들고, 저렴한 연산에서 "적립된" 비용을 추적하는 포텐셜 함수 Φ를 함께 보여줍니다 — 분할상환 비용(= 실제 비용 + ΔΦ)이 resize가 일어나는 순간에도 항상 일정 범위 안에 머무름을 증명합니다. 아직 미구현.

Jayverse에서의 위치

• Verex / Devnet: O(1)을 가정하기 전에 potential function으로 상각 비용을 증명한다. 크기가 늘어나는 어떤 구조든(오더북 레벨 배열, 인덱서의 확장 버퍼) resize-and-copy가 평균적으로 괜찮을 거라 가정하는 대신 Φ 논증을 한 번 적어둔다.
• gitboard: push마다 실제 비용을 진행 중인 potential과 함께 기록한다. 이렇게 하면 마켓별 확장 버퍼의 진짜 O(n) 회귀를 정상적이고 유한한 상각 스파이크와 구분할 수 있다.

← 전체 기술 노트 · 워크스페이스 인덱스 · 맨 위 ↑