Amortizovaná analýza

Amortizovaná časová složitost

  • Označuje časovou složitost algoritmu v sekvenci nejhorších vstupních dat

  • Na rozdíl od průměrné složitosti nevyužívá pravděpodobnosti a je proto zaručená

  • Jedná se jakoby o průměrnou složitost

  • Na rozdíl od asymptotické složitosti, která bere nejhorší možný čas

  • Označujeme

  • Asymptotickou složitost

  • K vypočtení se může použít Účetní metoda:

    • Každé operaci je přiřazena amortizovaná a skutečná cena
    • Pokud je amortizovaná větší, tak rozdíl vložíme na společný účet
    • Je li skutečná větší, tak rozdíl z účtu odebereme
    • V každém okamžiku musí být zůstatek na účtu nezáporný

Nafukovací pole

  • Některé inserty budou dlouhé (potřeba nafouknout a překopírovat pole)
  • Některé budou velmi rychlé
  • Amortizovaná složitost pro 1 insert je ale
    • U asymptotické mohl být 1 insert klidně až , pokud bychom vkládali až na konec pole
  • Časová složitost pro pole s prvky je v nejhorším případě

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