Speicherkomplexität berechnen?
Hey liebe gf-Community,
im Rahmen meines Studiums habe ich Übungsaufgaben zur Berechnung der Speicherkomplexität von Algorithmen bekommen. Selber mit Videos der Profs und googlen erschließt sich mir dieses Thema nicht.
Ich sehe den Pseudocode, den wir dafür analysieren sollen und habe keine Ahnung, was das mit irgendeinem Speicher zu tun hat. Das liegt wahrscheinlich auch daran, dass mir jegliche Vorkenntnisse über Informatik fehlen.
Kann mir jemand erstmal grundlegend erklären, was es damit auf sich hat und vielleicht an einem kleinen Beispiel eine solche Rechnung durchführen?
Im Gegensatz zur Zeitkomplexität, die für mich völlig logisch ist, habe ich hier weder Ansatz noch Wissen, noch Ahnung, wie ich mir selber weiter helfen kann. Danke.
1 Antwort
So wie bei der Zeitkomplexität hat auch die Aufwandskomplexität zwei Treiber:
Den skalierenden Faktor (also z.B. die Anzahl der Objekte oder die Rekursionstiefe oder ähnliches) und den Speicheraufwand je Objekt. Dies gilt es zu finden und dann geeignet in Beziehung zu setzen.
Selber mit Videos der Profs und googlen erschließt sich mir dieses Thema nicht.
Wie wäre es statt das Internet zu bemühen mal mit der Beschaffung von geeigneter Fachliteratur? Glaub mir, kein Script und kein Video kann ein gutes Buch ersetzen. Setze dich in die Unibibliotek in den Lesesaal, geh zum Informatik-Bereich und schau dir Bücher für Theoretische Informatik an bist du etwas gefunden hast mit dem du gut klar kommst.
Jedes Objekt welches du in einem Algorithmus verwendest benötigt Speicher. Beispiel: Wenn du ein Objekt hast welches aus einem 30 Zeichen langen Text besteht (Strasse in einer Adresse), so benötigt dieses 30 Bytes an Speicher. Wenn du nun n solcher Objekte in deinem Algorithmus verwendest (also n Datensätze mit je einem Straßennamen) dann benötigst du halt n*30 Bytes.
Komplexitätstheorie ist eben ein Thema der Theoretischen Informatik, und das findest du in der INformatik-Ecke der Bibliothek. Eine Auswahl aus Amazon:
https://www.amazon.de/Theoretische-Informatik-XLeitf%C3%A4den-Juraj-Hromkovic/dp/3835100432
usw.usf. wobei ich zur jeweiligen Qualität nichts sagen kann.
Ich weiß leider gar nicht, wonach ich suchen muss. Wie gesagt, mit Informatik habe ich nichts am Hut. Ich habe ja auch online nach Literatur geschaut. Aber ich verstehe schon die Grundlagen nicht. Was ist denn der Speicheraufwand? Wann brauche ich Speicher? Bei der Erstellung von Arrays? Wann bei Schleifen? Ich weiß nicht, wann man Speicher braucht.