Foren » 40. Bundeswettbewerb Informatik

[40.1 Allgemein] Effizienz in der Dokumentation

    • 23 Beiträge
    3. Oktober 2021 18:28:14 CEST

    Hallo,

    ich frage mich, ob man sich in der Dokumentation mit der Effizienz des Programms beschäftigen sollte? Damit meine ich, Dinge wie Big-O Notation, möglichst wenig durch Listen iterieren oder sogar Tests mit verschiedenen Verfahren durchzuführen, um das Programm möglichst effizient zu machen.

    Viele Grüße

    Christian

    • 17 Beiträge
    4. Oktober 2021 16:19:45 CEST

    Hallo Christian,

    die Laufzeit zu dokumentieren, ist auf jeden Fall sinnvoll. Besonders viel Wert wird darauf in der 2. Runde gelegt; es ist aber sehr hilfreich, sich damit in der 1. Runde schon vertraut zu machen.

    Dabei kommt es vor allem auf die Abschätzung der Laufzeit nach oben hin, also im Worst-Case, an (asymptotisch / in Groß-O-Notation); in Einzelfällen könnte es auch mal sinnvoll sein, z.B. die mittlere Laufzeit abzuschätzen. Asymptotisch vernachlässigbare Teile (z.B., ob durch eine Liste ein- oder zweimal iteriert wird) lässt man dabei außer Betracht.

    Tests mit dem/den Programm(en) durchzuführen, um die Laufzeit in der Praxis experimentell zu bestimmen, kann auch angebracht sein -- aber nur, wenn eine theoretische Analyse keine brauchbaren oder ausreichend bestimmten Ergebnisse liefert. Manchmal soll ein Programm ja nach einer Lösung eines Problems suchen und findet es dann viel schneller als man theoretisch zeigen konnte...