Binární sčítačka

  • Analýza amortizované složitosti

  • Uvažujme -bitovou sériovou sčítačku (ripple-carry)

  • Podporuje 2 operace:

    • Inc(n)
    • Add(n, m)

Složitost Inc()

  • Složitost počet inverzí bitů v binárním čísle
  • V nejhorším případě je tedy
  • Amortizovaná složitost je ale

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25