---

Geschrieben von Jessica am 03.04.2019 um 11:51:

  Was bedeutet es, wenn ein Algorithmus einen Aufwand von linear in der Eingabelänge hat?

Meine Frage:
Dijkstras Algorithmus hat eine Laufzeit von O(n^2).
Wenn man dichte Graphen einsetzt, also solche bei denen ein Graph mit n Knoten \Theta(n^2) Kanten besitzt, dann hat der Algorithmus eine lineare Laufzeit in der Eingabelänge.

Ich verstehe hier nicht den Zusammenhang. Ich meine, wie kanne sein, dass wenn der Input erhöht wird, die Laufzeit plötzlich geringer wird? Wie genau hängt der Aufwand von der Eingabelänge ab?

Meine Ideen:
Leider keinen Ansatz