Laufzeit LinkedList

Mariexshhx

Bekanntes Mitglied
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 ?
 

KonradN

Super-Moderator
Mitarbeiter
Wenn Du aus einer LinkedList alle Elemente löschst, dann hast Du ein O(1). Du willst also genauer sein mit den Angaben. Wenn n die Anzahl der Elemente in der Liste ist und Du n Elemente löschen willst, dann kannst Du einfach den Head setzen und daher hast Du ein O(1). Wenn du aber m Elemente löschen willst, dann hast Du ein O(n*m).
 

Mariexshhx

Bekanntes Mitglied
Also es geht darum das ich eine Liste habe die aus zahlen besteht ich möchte immer die zahl in der Liste addieren und danach dieses Element der Liste entfernen. Am Ende gebe ich die Summe zurück. Das addieren hat ja einen konstanten aufwand O(1) aber beim entfernen weiß ich es halt nicht
 

KonradN

Super-Moderator
Mitarbeiter
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?
 

Mariexshhx

Bekanntes Mitglied
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 ?
 

KonradN

Super-Moderator
Mitarbeiter
Wenn Du alle Elemente einer Liste behandeln willst: Wieso musst Du da einen Vorgänger finden? Du nimmst doch das erste Element!
 

Mariexshhx

Bekanntes Mitglied
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?
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 ?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M verbesserte Laufzeit bei LinkedList Allgemeine Java-Themen 7
S Build-Zeitpunt (Datum und Uhrzeit) irgendwie während der Laufzeit zugänglich machen..? Allgemeine Java-Themen 4
M Laufzeit des Prim Algorithmus Allgemeine Java-Themen 3
K Verbesserung der Laufzeit beim Sortieren von Einwohnern nach ihrem Geburtsjahr Allgemeine Java-Themen 0
H was ist den dieses zur Kompilierzeit und zur Laufzeit in Java? Allgemeine Java-Themen 3
L Classpath Zur Laufzeit bestimmte Klassen in Classloader hinzufügen? Allgemeine Java-Themen 4
L Compiler-Fehler Google Guice Module zur Laufzeit zusammenstellen und binden Allgemeine Java-Themen 4
J Jasper Reports - Subreport zur Laufzeit ändern Allgemeine Java-Themen 6
O jar und EXE Dateien, Pfade zur Laufzeit Allgemeine Java-Themen 1
T Externe Java Klasen zur Laufzeit einbinden Allgemeine Java-Themen 10
X Collections Gibt es eine Klasse welche die Vorteile von List und HashMap vereint, aber konstante Laufzeit (O(1)) hat in Java? Allgemeine Java-Themen 4
D Boolean von ein anderem Java Programm während der Laufzeit ändern Allgemeine Java-Themen 23
N Generic Type einer Generischen Klasse während der Laufzeit bekommen Allgemeine Java-Themen 2
J .java-Dateitext Compile zur Laufzeit ohne File Allgemeine Java-Themen 15
kodela Daten während Laufzeit zugriffsbereit Allgemeine Java-Themen 15
Neumi5694 Interpreter-Fehler final Eigenschaft während Laufzeit geändert Allgemeine Java-Themen 2
A Java Klasse auf Tomcat während der Laufzeit austauschen Allgemeine Java-Themen 1
M Sinn von Kompilierung zur Laufzeit Allgemeine Java-Themen 3
T Java Class Intrumentation mit Annotations in Laufzeit Allgemeine Java-Themen 1
S Byte Array welches in Laufzeit aufgelöst wird // Objekt Array Allgemeine Java-Themen 3
T Dateien zur Laufzeit in Java-Programm packen? Allgemeine Java-Themen 3
S Laufzeit Primzahlgenerator Allgemeine Java-Themen 18
S Zur Laufzeit Klasse mit einer anzahl von X Objekten erstellen Allgemeine Java-Themen 5
F Classpath Programmteile zur Laufzeit nachladen Allgemeine Java-Themen 6
D Variablen zur Laufzeit global speichern (Registry Pattern?) Allgemeine Java-Themen 6
H ResourceBundle während Laufzeit bearbeiten Allgemeine Java-Themen 3
J Input/Output Jar-Datei zur Laufzeit erweitern Allgemeine Java-Themen 13
P Generic zur Laufzeit Allgemeine Java-Themen 4
A ar während der Laufzeit überschreiben Allgemeine Java-Themen 20
X MergeSort Laufzeit Problem Allgemeine Java-Themen 4
J Resourcen waehrend der Laufzeit aendern? Allgemeine Java-Themen 9
P Wie bei log4j den Dateipfad der Logdatei zur Laufzeit ändern? Allgemeine Java-Themen 3
X Update einer Jar während der Laufzeit Allgemeine Java-Themen 8
T Klassen Fabrik (Factory) zur Laufzeit erweitern Allgemeine Java-Themen 5
S UML zur Laufzeit ändern Allgemeine Java-Themen 10
E Wert von enum zur Laufzeit festlegen. Allgemeine Java-Themen 5
L Methode in Thread mit langer Laufzeit unterbrechen (ANT executeTarget) Allgemeine Java-Themen 4
O Problem bei Darstellung der Laufzeit eines Programms Allgemeine Java-Themen 3
hdi Ressourcen dynamisch zur Laufzeit laden Allgemeine Java-Themen 15
A Wie zur Laufzeit auf Objekte zugreifen Allgemeine Java-Themen 7
N variable Anzahl von Objektinstanzen zur Laufzeit erstellen Allgemeine Java-Themen 4
P Java Konsole zur Laufzeit einblenden Allgemeine Java-Themen 4
P Klassenwahl zur Laufzeit Allgemeine Java-Themen 5
R Objekt zur Laufzeit zerstören? Allgemeine Java-Themen 12
E formartierte Ausgabe zur Laufzeit Allgemeine Java-Themen 2
Sonecc Zugriff auf Class File einer anderen Jar während der Laufzeit Allgemeine Java-Themen 2
F Wie zur Laufzeit ganz neue Objekte erzeugen? Allgemeine Java-Themen 5
T Class-files zur Laufzeit zu Reflection-Zwecken laden Allgemeine Java-Themen 18
DamienX Debug Modus zur Laufzeit erkennen Allgemeine Java-Themen 3
Stillmatic Debuggen/ Laufzeit von Methoden Allgemeine Java-Themen 2
Dragonfire Generic Typ zur Laufzeit Allgemeine Java-Themen 9
M Klasse zur Laufzeit ersetzen Allgemeine Java-Themen 10
S Wie gross ist die Laufzeit für diese Schleife?? Allgemeine Java-Themen 8
G File zur Laufzeit erzeugen Allgemeine Java-Themen 4
G Jar File zur Laufzeit ändern. Allgemeine Java-Themen 4
T Java - Compilieren während Laufzeit Allgemeine Java-Themen 3
Y JARs austauschen zur Laufzeit Allgemeine Java-Themen 11
G Datenbank zur laufzeit wechseln Allgemeine Java-Themen 11
C Innere Klassen zur Laufzeit Instanzieren Allgemeine Java-Themen 4
T Zur Laufzeit erben? Allgemeine Java-Themen 22
L HashMap / Objekte auf Festplatte zur Laufzeit auf HD swappen Allgemeine Java-Themen 7
L Zur Laufzeit eine Klasse laden, die auf jar-File zugreift Allgemeine Java-Themen 15
V Java-Programm weiss zur Laufzeit wie es gestartet wurde? Allgemeine Java-Themen 6
N Endlosschleifen automatisiert erkennen (Code oder Laufzeit)? Allgemeine Java-Themen 6
G Eindeutiges Identifizieren einer JTable/Component z.laufzeit Allgemeine Java-Themen 2
G Datei durchsuchen, lange Laufzeit! Allgemeine Java-Themen 2
A log4j 1.3 und ändern der log Konfiguration zur Laufzeit Allgemeine Java-Themen 4
Apo Zur Laufzeit Klassen mit Packages laden? Allgemeine Java-Themen 2
G genauen Typ einer generischen Klasse zur Laufzeit ermitteln Allgemeine Java-Themen 2
F Typ eines Objekts zur Laufzeit bestimmen? Allgemeine Java-Themen 8
T xverify-parameter : Workaround zur Laufzeit? Allgemeine Java-Themen 8
M Bibliotheksname zur Laufzeit ermitteln (Classloader) Allgemeine Java-Themen 7
G Klasse wird zur Laufzeit nicht gefunden? Allgemeine Java-Themen 3
@ zur Laufzeit Interface aus jar implementieren? Allgemeine Java-Themen 5
MQue Laufzeit Allgemeine Java-Themen 4
D Lautstärke einzelner AudioClips zur Laufzeit verändern Allgemeine Java-Themen 4
C Mathefunktion zur Laufzeit einlesen und dann verarbeiten Allgemeine Java-Themen 13
G Klassen zur Laufzeit einbinden Allgemeine Java-Themen 3
J Bibliotheken erst zur Laufzeit laden Allgemeine Java-Themen 5
R Drag und Drop - Fehler während Laufzeit Allgemeine Java-Themen 14
byte Generic Type einer List zur Laufzeit rausfinden? Allgemeine Java-Themen 4
A Class File zur Laufzeit laden ohne den Binary Name zu kennen Allgemeine Java-Themen 11
M Überprüfen einer zur Laufzeit geladenen Klasse Allgemeine Java-Themen 3
H Klassen aus einem Ordner zur Laufzeit laden. Allgemeine Java-Themen 6
S Laufzeit und Compilefehler Allgemeine Java-Themen 6
S JPanel zur Laufzeit verbergen bzw. wieder anzeigen lassen Allgemeine Java-Themen 4
F Objektname zur Laufzeit festlegen? Allgemeine Java-Themen 12
I Sprache zur Laufzeit des Programms ändern Allgemeine Java-Themen 3
G Laufzeit eines aus Java gestarteten Programms beobachten Allgemeine Java-Themen 3
S Log4J: Logdatei zur Laufzeit ermitteln. Allgemeine Java-Themen 2
I Zur Laufzeit ermitteln, ob Klasse in JAR-Datei Allgemeine Java-Themen 2
R iText.jar wird zur Laufzeit nicht gefunden Allgemeine Java-Themen 4
J ResourceBundle / properties-datei während der Laufzeit verän Allgemeine Java-Themen 6
H Methode einer zur Laufzeit generierten Instanz aufrufen Allgemeine Java-Themen 2
M Formel in einem String während Laufzeit berechnen. Allgemeine Java-Themen 4
O Werte einer Generic LinkedList zusammenrechenen Allgemeine Java-Themen 14
M Delete bei sortierter LinkedList Allgemeine Java-Themen 5
M ArrayList oder LinkedList Allgemeine Java-Themen 10
L Unterschied zwischen List und LinkedList implementierung? Allgemeine Java-Themen 15
K Gespeicherte Daten von einer LinkedList auf vier LinkedList verteilen Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben