Komplexitätsbetrachtung anhand von Kurven

NetzUnity und Informatik-forum wurden zusammengelegt. Eine entsprechende Ankündigung wird demnächst noch folgen. Für 2025 ist hier einiges geplant! Bei Fragen bitte per DM an Maximilian Rupp wenden.

    Hallo Forum,
    ich habe zwei Algorithmen gemessen und in folgendem Diagramm dargestellt:

    Um herauszubekommen ob die Komplexitäten diesselben sind habe ich den Laufzeitwert von solve an der Stelle 3000 mit einem konstanten Faktor F multipliziert, sodass das Produkt dem Laufzeitwert von solveBPB entspricht.

    Nun alle Messwerte von solve mit diesem Faktor F multipliziert und folgenden Graph erhalten:

    Die Kurve des gelben graphen steigt ja nun scheinbar viel stärker an als die kurve des roten graphen. Kann ich schlussfolgern, dass die Komplexität von solveBPB geringer ist als von solve (da F*solve stärker ansteigt) und solve bpb für diese werte somit nur durch einen konstanten faktor geringer ist?

    idealer wäre wahrscheinlcih eine analyse des algorithmus, da die messungen in der regel nicht besonders aussagekräftig sind. vor allem wenn n nur so klein ist. aufwandsabschätzungen machen eher sinn wenn n gegen unendlich strebt.

    aber da gibts sicher leute die sich damit besser auskennen als ich. was für eine art von algorithmus ist es denn?

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden