Chrise
24-05-2003, 19:33
Ich hab mir die zusammensetzung der laufzeit von DFS auf seite 116 angeschaut, und frage das jetzt nur, um sicher zu gehen, das ich das einigermaßen verstanden habe:
analyse der laufzeit:
insgedamt ergibt dies kosten von:
O(|V|)+summeO(d(v))=O(|V|)+O(|E|)
wenn man ganz genau wäre würde es doch heißen:
O(|V|)+summeO(d(v))=O(|V|)+O(2*|E|) , da ja jede kante, von jedem Punkt aus einmal aufgerufen wird, als von immer genau 2 punkten aus.
Da 2 aber ein konstanter Faktor ist, kann man es weg lassen...
stimmt das so???
analyse der laufzeit:
insgedamt ergibt dies kosten von:
O(|V|)+summeO(d(v))=O(|V|)+O(|E|)
wenn man ganz genau wäre würde es doch heißen:
O(|V|)+summeO(d(v))=O(|V|)+O(2*|E|) , da ja jede kante, von jedem Punkt aus einmal aufgerufen wird, als von immer genau 2 punkten aus.
Da 2 aber ein konstanter Faktor ist, kann man es weg lassen...
stimmt das so???