Laufzeit,Adjazenzmatrix < Algorithmen < Schule < Informatik < Vorhilfe
|
| Aufgabe | Bestimmen Sie den Aufwand der folgenden Operationen in O-Notation für die Adjazenzmatrix- und die Adjazenzlisten-Darstellung!
Einfügen einer Kante |
Hallo, ich würde mich über Tipps wie man die Lösung für die oben genannte Aufgabe bestimmen kann.
Mein Ansatz:
G=(V,E) wobei V Anzahl der Knoten und E Anzahl der Kanten des Graphen sind.
gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:50 Mi 07.07.2010 | | Autor: | felixf |
Moin!
> Bestimmen Sie den Aufwand der folgenden Operationen in
> O-Notation für die Adjazenzmatrix- und die
> Adjazenzlisten-Darstellung!
>
> Einfügen einer Kante
>
> Hallo, ich würde mich über Tipps wie man die Lösung
> für die oben genannte Aufgabe bestimmen kann.
>
> Mein Ansatz:
>
> G=(V,E) wobei V Anzahl der Knoten und E Anzahl der Kanten
> des Graphen sind.
Schreib doch mal Pseudocode auf fuer die entsprechenden Faelle. Wenn dieser detailliert genug ist, kann man daraus den Aufwand ablesen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:44 Mi 07.07.2010 | | Autor: | capablanca |
Hallo, danke für die Antwort, ich habe es rausgefunden, müsste eigentlich stimmen.
Adjazenzmatrix: O(1)
Adjazenzliste: O(1)/O(n)
gruß
|
|
|
|
