Informatiker, kennt ihr gute Bücher, wo die Komplexität der Algorithmen ausführlich erklärt wird?

...komplette Frage anzeigen

1 Antwort

Naja das ist eigentlich recht einfach mit der Komplexität breitensuche. In der queue sind maximal E-viele Knoten. Beim vollständigen entdecken eines Knoten werden alle adjazenten Knoten genau einmal entdeckt. Also wird jede kante maximal einmal durchlaufen. Das sind insgesamt V-viele kanten. Also brauch das entleeren der queue E und das aufdecken aller Knoten.In Summe V Durchläufe => O(|E|+|V|) .. Weiß jetzt nicht ob ich das noch 100% richtig in Erinnerung habe. Aber klingt für mich eigentlich logisch beim schreiben.

tente1 30.07.2015, 19:41

ups meinte für Knoten V-viele und für Kanten E-viele... Wir hatten die deutsche Bezeichnung E für Ecke und K für Kante. Deswegen kam ich mit E für Edge statt Ecke durcheinander.

0

Was möchtest Du wissen?