Kosten für Adjazenzmatrix- und listen |
| 25.05.2010, 21:06 | banausor | Auf diesen Beitrag antworten » |
| Kosten für Adjazenzmatrix- und listen ich habe eine wichtige Abgabe und will da ganz sicher gehen: Bei einem ungerichteter Graph G=(V,E), die Kosten in der O-Notation angeben für Adjazenzmatrix-Datenstruktur und -liste: 1. Entfernen einer Kante {i,j} Matrix: O(i) Liste: O(deg(i) + deg(j)) 2. Alle Nachbarn eines Knotens i finden: Matrix: O(|V|} Liste: O(deg(i)) Stimmt das so? Wenn in der Aufgabe steht, dass ich das angeben soll, soll ich da noch groß was beweisen? |
||
| 26.05.2010, 12:27 | Uni Mannheim | Auf diesen Beitrag antworten » |
| RE: Kosten für Adjazenzmatrix- und listen also erstmal sollst du dein übungsblatt selber machen. 2. : du sollst es natürlich beweisen. sonst kannste auch einfach überall den passenden Satz aus der Vorlesung als Grund drunter schreiben und bist fertig. denkst du, dafür bekomsmt du 8 punkte??? o_O |
||
| 26.05.2010, 15:35 | Reksilat | Auf diesen Beitrag antworten » |
| RE: Kosten für Adjazenzmatrix- und listen @Uni Mannheim: Er macht doch sein Übungsblatt selbst. Spricht etwas dagegen, hier bei Problemen nachzufragen? @banausor: In der O-Notation geht es um die Kosten, die allgemein bei einer gewissen Aktion entstehen. Es ist insofern nicht sinnvoll i und j zu verwenden, die ja für jede Kante des Graphen anders sind. Hilfreich sind hier die Parameter |V|, |E| und evtl. maxdeg(G). Und die Frage, ob man etwas auch beweisen soll, ist in einem Internetforum denkbar schlecht aufgehoben. Woher soll das ein völlig Fremder wissen? - Hier hat es sich ja glücklicherweise doch noch geklärt. 
Gruß, Reksilat. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
