Hey,
ich hatte eine Frage wegen der Laufzeit. Z.B. löst mein jetziger Algorithmus für 2a) “Kaese7.txt” mit 1.5 Millionen Scheiben in circa 25 Sekunden. Gerade habe ich es in Python, in c++ könnte ich es höchstwahrscheinlich noch auf weniger als 1 Sekunde hinkriegen. Somit ist meine Frage, ob es irgendeine obere Schranke für die Laufzeit gibt und außerdem, ob ich es für die Laufzeit noch mal in c++ implementieren soll oder es in Python lassen kann.
VG
Hallo Robin,
wichtig ist hauptsächlich die Laufzeit deines Algorithmus. Auf die Programmiersprache kommt es eigentlich nicht an - zumindest bei den eher theoretischen Überlegungen in der Dokumentation. Die "praktische" Laufzeit kann, wie du auch sagst, deutlich davon abhängen, ob man eine Programmiersprache mit bekanntermaßen sehr guten Compilern wählt oder eine interpretierte Sprache. Aber der Algorithmus wird durch die Wahl der Sprache nicht besser. Für den Bundeswettbewerb Informatik ist sie deshalb meist nicht von besonderem Belang.
Ich verstehe das jetzt nicht ganz. Was genau ist mit Laufzeit gemeint, die Zeit die das Programm zum kompilieren brauchen würde, oder die Programm die das Programm läuft? Bei A3 hätte ich im ersten Fall überhaupt keine Problem, im zweiten Fall ist das Programm allerdings sehr lange dran.
Wenn wir von Laufzeit reden, dann meinen wir die theoretische Laufzeit. Dafür ist die Zeit für das Kompilieren egal und sie ist unabhängig von der Rechenleistung.
Um die Laufzeit formal zu notieren wird meist die "Landau-Notation" verwendet. Schau doch mal hier, vielleicht hilft das weiter: https://de.wikipedia.org/wiki/Landau-Symbole oder ein wenig ausführlicher, aber auf Englisch: https://en.wikipedia.org/wiki/Big_O_notation
Wie eine Laufzeitanalyse bei unseren Aufgaben aussehen kann, kannst du dir auch in den Lösungshinweisen der vergangenen Jahre anschauen :)