1
Graph als Adjazenzmatrix Zeitkomplexität
I verstehen nicht, warum eine Kante in Adjazenzmatrix Einsetzen nimmt O (1) Zeit. Zum Beispiel wollen wir eine Kante von Scheitelpunkt 3 bis 5 hinzufügen, im orientierten Graphen müssen wir den Graphen [2] [4] zu 1 ändern. In oriented geht es auch umgekehrt. Wie kann es möglich sein, O (1), wenn wir mindestens einmal die richtige Zeile in Array suchen müssen, so ist es bereits O (| V |)?
Die Zeit zum Einfügen einer Kante hängt nicht von der Anzahl der Scheitelpunkte oder Kanten ab. Die Adjazenzmatrix hat die gleiche Anzahl von Zeilen und Spalten, nämlich die Anzahl der Eckpunkte. Daher erfordert der Zugriff auf eine bestimmte Kante keine Suche. Dieses konstante Verhalten wird als O (1) ausgedrückt. –
Die Annahme besteht darin, dass Ihre Matrix mit einer Datenstruktur implementiert wird, die einen konstanten Zugriff auf eine beliebige Zelle ermöglicht und keine 2D-Entsprechung einer verknüpften Liste darstellt. – chepner
"finde die richtige Zeile im Array" - wenn es sich um ein Array handelt, "findet" das Finden der Zeile nur in das Array. Also O (1). Es gibt kein "Suchen", Sie haben bereits den Index. – harold