Fehler im Video Kruskal

DenK
Erstie
Erstie
Beiträge: 14
Registriert: 26. Apr 2013 19:13

Fehler im Video Kruskal

Beitrag von DenK »

Hallo,
ich glaube ich habe einen Fehler in der asymptotischen Komplexität entdeckt, bzw. ist es im Wiki richtig. Die Komplexität ist statt der im video gesagten (n * T(n)+ m * log(m)) wohl eher (m* T(n)+ m * log(m)).

Die Uniteoperation muss ja genau |V|-1 mal durchgeführt werden und ist daher genau gleich Anzahl der Kanten.

Ich hoffe das ist richtig, sonst wäre ich für eine kurze Erklärung sehr dankbar.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Video Kruskal

Beitrag von Prof. Karsten Weihe »

DenK hat geschrieben: Die Uniteoperation muss ja genau |V|-1 mal durchgeführt werden und ist daher genau gleich Anzahl der Kanten.
Ja, gleich Anzahl der Kanten im Baum. Aber \(m\) ist die Anzahl der Kanten im Eingabegraphen.

KW

DenK
Erstie
Erstie
Beiträge: 14
Registriert: 26. Apr 2013 19:13

Re: Fehler im Video Kruskal

Beitrag von DenK »

Danke!

Das bedeutet dass (n * T(n) + m * log(m)) richtig ist? Dann müsste das im Wiki geändert werden, denn die unite-Operation wird ja auf jedenfall n-mal ausgeführt und nicht m-mal. Viele Kanten fallen ja durch die find-Operation mit konstanter Laufzeit schon raus.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Video Kruskal

Beitrag von Prof. Karsten Weihe »

Hmh, der Witz ist: Beides ist richtig. 8)

Mehr als n-mal geht nicht, weil die Grundmenge nur aus n Elementen besteht.

Mehr als m-mal geht ebenfalls nicht, weil es nur m Iterationen gibt.

KW

DenK
Erstie
Erstie
Beiträge: 14
Registriert: 26. Apr 2013 19:13

Re: Fehler im Video Kruskal

Beitrag von DenK »

Ok, alles klar danke! Wenn beides richtig ist gibt es weniger Möglichkeiten Fehler zu machen, auch gut :)

stef
Erstie
Erstie
Beiträge: 16
Registriert: 25. Sep 2012 14:59

Re: Fehler im Video Kruskal

Beitrag von stef »

Hallo,
ich hätte da auch noch mal eine Frage zu dem Video.
Auf der Folie wo der Min Spanning Tree zu sehen ist sagt Hr. Weihe das die größte Kantenlänge 13 ist.
Aber ich seh auf der Folie nur die längste Kantenlänge zwischen v1 und v6 mit 12? Oder wird die Kantenlänge mit 13 irgendwie berechnet?

Wenn die 12 richtig ist wäre ja dann auch die Berechnung für dem Max Spanning Tree mit der 12 oder?

Viele Grüße

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: Fehler im Video Kruskal

Beitrag von AnnaW »

Darüber bin ich gerade auch gestolpert. 12 sollte schon richtig sein, oder?

Viele Grüße

Anna

Antworten

Zurück zu „Archiv“