Die Laufzeit von delete beträgt ja O(n) wenn ich nun n Elemente lösche hab ich dann eine Laufzeit von O(n*n)? Oder wie muss man das verstehen ?
also das summieren hat ja jedes mal konstanten Aufwand O(1) also quasi für n Elemente der Liste n * O(1) wenn ich das richtig sehe ? Für das löschen muss ja bei einfach verketteten Listen der Vorgänger gefunden werden was auch O(n) dauert das Umlegen der zeiger hat wieder konstanten Aufwand also O(1). Also habe ich für jedes Element einen Aufwand von O(1) + O(n) ? Das wäre doch wiederrum O(n) richtig ?Du hast eine LinkedList und willst: Die Werte durchgehen und summieren und dabei aus der Liste entfernen?
Dann überlege einmal, die die Liste aufgebaut ist, was für Schritte wären notwendig? Welche Komplexität ergibt sich dann daraus?
also das summieren hat ja jedes mal konstanten Aufwand O(1) also quasi für n Elemente der Liste n * O(1) wenn ich das richtig sehe ? Für das löschen muss ja bei einfach verketteten Listen der Vorgänger gefunden werden was auch O(n) dauert das Umlegen der zeiger hat wieder konstanten Aufwand also O(1). Also habe ich für jedes Element einen Aufwand von O(1) + O(n) ? Das wäre doch wiederrum O(n) richtig ?
Ja genau, und das halt dann n Mal, so dass Du bei O(n) sein wirst.warte mal du hast vollkommen recht ich lösche ja so gesehen immer das erste Element und Löschen am Anfang hat einen Aufwand von O(1) wenn ich richtig liege?
und wegen dem addieren habe ich ja auch jeweils O(1) n mal ?Ja genau, und das halt dann n Mal, so dass Du bei O(n) sein wirst.
also trotzdem noch O(n)?Ja genau, und das halt dann n Mal, so dass Du bei O(n) sein wirst.