04 Binární sčítačka
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Binární sčítačka
Analýza amortizované složitosti
Uvažujme $k$-bitovou sériovou sčítačku (ripple-carry)
Podporuje 2 operace:
- Inc(n)
- Add(n, m)
# Složitost Inc()
- Složitost $\mathrm{Inc}(n) =$ počet inverzí bitů v binárním čísle $n$
- V nejhorším případě je tedy $\le k$
- Amortizovaná složitost je ale $O^*(1)$