On the amortized complexity of approximate counting
https://arxiv.org/abs/2211.03917 On the amortized complexity of approximate counting (상각 복잡도 근사 계산) Abstract 값 n까지의 카운터를 단순히 저장하는 것은 Ω(log n)비트의 메모리가 필요. Nelson과 Yu [NY22]는 Morris의 연구 [Mor78]를 따라, 쿼리 응답이 (1+ϵ)-근사값이며 확률적으로 최소 1-δ를 만족한다면 O(log(logn)+log(log(1/δ)+log(1/ϵ))비트만이 필요하며, 사실 이 경계는 최적이다. Morris의 원래 연구 동기와 현대 응용 프로그램은 하나의 카운터를 유지하는 것뿐만 아니라 k개의 카운터를 유지해야한다. 이로 인해 다음 질문이 생긴다. k개의 카운터를 유지하면서 ..