Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Was bedeutet es, wenn ein Algorithmus einen Aufwand von linear in der Eingabelänge hat? » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Was bedeutet es, wenn ein Algorithmus einen Aufwand von linear in der Eingabelänge hat?
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Jessica
Grünschnabel


Dabei seit: 03.04.2019
Beiträge: 1

Was bedeutet es, wenn ein Algorithmus einen Aufwand von linear in der Eingabelänge hat? Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
03.04.2019 11:51 Jessica ist offline E-Mail an Jessica senden Beiträge von Jessica suchen Nehmen Sie Jessica in Ihre Freundesliste auf
Daki Savic
Grünschnabel


Dabei seit: 18.04.2019
Beiträge: 7

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

schon was gefunen?
18.04.2019 01:33 Daki Savic ist offline Beiträge von Daki Savic suchen Nehmen Sie Daki Savic in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Was bedeutet es, wenn ein Algorithmus einen Aufwand von linear in der Eingabelänge hat?