Laufzeitberechnung / Laufzeitanalyse

[fkerber]

Hi!

Für mein Projekt muss ich eine Laufzeitanalyse eines Algorithmus machen. Bei der Durchführung des Algorithmus kann man drei Sachen einstellen:

N: Anzahl Städte (Problemgröße)
A: Anzahl A
I: Anzahl I

Jetzt bin ich hingegangen und hab mir bei immer gleichem I und A angeschaut, wie sich die Zeit bei Änderung von N verändert.
Dabei ist rausgekommen, was man im Anhang 1 sieht. So wie ich das interpretiere verhält sich der Algorithmus also quadratisch. Wenn man sich das ganze näher betrachtet, so führe ich den Graph auf folgendes zurück:

Zitat:

Laufzeit < (I/100 * A/100 * N²)

Soweit so gut, allerdings haben die Zahlen I und A ja auch eine Bedeutung. Genauergesagt muss man bei großem (oder größeren) N die Zahlen A und I ebenfalls erhöhen, da der Algorithmus sonst keine guten Ergebnisse liefert. Durch etwas rumexperimentieren habe ich also näherungsweise jeweils die kleinsten I und A (für verschiedene N) ermittelt, sodass noch gute Ergebnisse rauskommen.
Dann ergibt sich in etwa ein solcher Graph, wie in Anhang 2 zu sehen.

So, jetzt zur eigentlichen Frage:
Zählt nur die quadratische Ordnung (also egal mit welchem Ergebnis)? oder zählen die "realen" Werte? Falls die realen Werte zählen, hat jemand ne Idee, wie diese Funktion ungefähr läuft? (Sie steigt ja stärker als x², weniger stark als x³, ne e-Funktion iss auch keinesfalls....)

Ciao und danke
Frederic

[marabu]

Guten Morgen, Frederic.

Oft kann gar keine genaue Laufzeit-Funktion angegeben werden. Man behilft sich durch eine Abschätzung nach oben. Interessant ist nur das am schnellsten wachsende Glied des Polynoms - der Rest und etwaige Konstanten fallen unter den Tisch.

Grüße vom marabu

[fkerber]

Hi!

Ja, das ist mir im Prinzip klar. Allerdings weiß ich halt nicht, ob überhaupt die "realen" Werte von Bedeutung sind oder nur die Abschätzung bei gleichem A und I?

Was wäre denn bei den realen Werten das schnellwachsendste Glied? Immer noch x², oder?


Ciao Frederic

[Gausi]

Wenn die Laufzeit bei dir von A, I und N abhängt, und deine Formel stimmt, dann ist die Laufzeit deines Algorithmus quadratisch in N, und linear in A bzw. I.
Wenn N, A und I unabhängig voneinander gewählt werden können, bist du mit der Laufzeitabschätzung fertig - mehr kann man nicht machen ;-)
Wenn du A und I generell durch eine Konstante nach oben beschränken kannst, dann ist deine Laufzeit generell quadratisch. (Das scheint aber nicht so zu sein.)

Wenn du mit wachsendem N auch größere I bzw. A benötigst, dann stellt sich die Frage, wie stark müssen A und I anwachsen? Linear in N? Oder wie Log(N)?
Im ersten Fall wäre dann deine Laufzeit in O(N^4), im zweiten Fall in O((N*logN)^2).

[fkerber]

Hi!

@Gausi:
Danke für deine Ausführungen. Ich werde heut mittag mal versuchen, das ganze nachvollziehen zu können.

Ciao Frederic