Algorithmen und Datenstrukturen · Senior · Frage 28 von 75
Was ist amortisierte Analyse mit der „Buchhaltungs“- oder „Potenzial“-Methode?
- 1Die Zeit einer Operation viele Male messen und mitteln
- 2Günstige Operationen bezahlen die seltenen teuren mit
- 3Die Laufzeit über zufällige Eingaben mitteln
Antwort zeigen
Richtige Antwort: Günstige Operationen bezahlen die seltenen teuren mit
Erklärung
Sie liefert eine Schranke für den schlimmsten Fall einer Folge von Operationen, ganz ohne Wahrscheinlichkeit. Jedes push in ein dynamisches Array „spart“ eine Konstante, die später das Kopieren beim Vergrößern bezahlt. Mitteln über zufällige Eingaben ist Average-Case-Analyse, etwas anderes.