11.2 Floyd Warshall

michael123
Neuling
Neuling
Beiträge: 3
Registriert: 16. Apr 2013 17:35

11.2 Floyd Warshall

Beitrag von michael123 »

Wenn ich das richtig verstanden habe beschreibt die Komplexität des Algorithmus Floyd Warshall ja nur das setzen einzelner Matrixeinträge, oder?

Oder anders gesagt: Worin besteht überhaupt der Unterschied zwischen der Komplexität O(n³) und der Anzahl zu setzenden Matrixeinträgen?
Also entweder ist die Lösung vor meiner Nase oder ich denke falsch :D

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 11.2 Floyd Warshall

Beitrag von JannikV »

Die Komplexität bezieht sich wie immer auf den kompletten Durchlauf des Algorithmus. Die wesentliche Operation ist das Setzen von Matrixeinträgen, die hier gezählt werden. Und das sind in der Größenordnung n³

VG

alexanderheinrich
Erstie
Erstie
Beiträge: 12
Registriert: 17. Apr 2013 11:47

Re: 11.2 Floyd Warshall

Beitrag von alexanderheinrich »

Das heißt doch, dass ich um eine möglichst genaue Anzahl zu bekommen nicht die Vereinfachungen, die bei der Berechnung der Komplexität vorgenommen werden, machen darf, sondern einfach mit ziehen.

Habe ich das jetzt falsch verstanden?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 11.2 Floyd Warshall

Beitrag von JannikV »

Du sollst halt eine Funktion f(n) angeben die abschätzt wie oft "Setzen eines einzelnen Matrixeintrags" ausgeführt wird.

Keks
Neuling
Neuling
Beiträge: 8
Registriert: 28. Mai 2013 21:53

Re: 11.2 Floyd Warshall

Beitrag von Keks »

Ich glaub ich stehe auch auf dem Schlauch - da jeder Matrixeintrag in jeder Iteration angefasst wird, sind es doch genau n³ Ausführungen oder nicht?

mo2l
Neuling
Neuling
Beiträge: 4
Registriert: 4. Mai 2013 16:42

Re: 11.2 Floyd Warshall

Beitrag von mo2l »

Wäre es wenn wir n mal die Iteration durchführen würden.

Keks
Neuling
Neuling
Beiträge: 8
Registriert: 28. Mai 2013 21:53

Re: 11.2 Floyd Warshall

Beitrag von Keks »

Was doch auch der Fall ist?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 11.2 Floyd Warshall

Beitrag von JannikV »

Basis!? ...

mo2l
Neuling
Neuling
Beiträge: 4
Registriert: 4. Mai 2013 16:42

Re: 11.2 Floyd Warshall

Beitrag von mo2l »

Also laut Wiki habe ich zu mindestens keine n Iterationen die ich durchlaufe.

Keks
Neuling
Neuling
Beiträge: 8
Registriert: 28. Mai 2013 21:53

Re: 11.2 Floyd Warshall

Beitrag von Keks »

die Basiseinträge zählen auch? Ich dachte, die bekommt man schon übergeben und muss sie nicht erst eintragen.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 11.2 Floyd Warshall

Beitrag von JannikV »

Nö, das ist Teil des Algorithmus.

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: 11.2 Floyd Warshall

Beitrag von robertH »

sollte es in dem Wiki http://wiki.algo.informatik.tu-darmstad ... d-Warshall nicht heißen, dass n anstatt n-1 Iterationen benötigt werden?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 11.2 Floyd Warshall

Beitrag von JannikV »

Hey, das stimmt. Ich habs korrigiert.

VG

Antworten

Zurück zu „Archiv“