Laufzeitanalyse Liste

[alexschmid97]

Hey,
Ich muss eine Aufgabe zur Laufzeitanalyse von Listen bearbeiten. Jetzt bin gerade an folgendem Punkt und komm nicht weiter...

Ich soll das O-Kalkül für das einfügen von Elementen in ein Array, einfache Liste, doppelt verkette Liste angeben.

Das müsste doch bei allen O(n) sein oder ?
Aber eine Liste ist doch in der Theorie schneller als ein Array, da ja nur die Verweise neu gesetzt werden müssen ?

 

[Tarrew]

Das eigentliche Einfügen eines Elements in ein Array, also zB. "array[0]=5" hat eine Komplexität von O(1).

Für LinkedList gilt imo, dass am Head oder Tail einfügen auch eine Komplexität von O(1) hat und alles andere eine Komplexität von O(n).

 

[alexschmid97]

also gilt nur für eine doppelt verkettete Liste O(n) ?

 

[Tarrew]

add(i, element)

hat sowohl bei einer einfach verketten als auch bei einer doppelt verketteten Liste eine Komplexität von O(n). Wenn i=0 bzw. i=list.size() (also am Head bzw Tail einfügen) dann ist die Komplexität O(1).

 

[alexschmid97]

ahh stimmt natürlich, dann wäre es ja beim Löschen der Elemente genau das gleiche, weil die Ansprechnung der Werte ja praktisch das selbe ist

 

[Tarrew]

Genau. Wobei ich mich korrigieren muss.
Bei einer einfachen LinkedList ist die Komplexität nur O(1) beim Einfügen/Löschen beim Head. Verweis auf Tail gibt es wohl nur bei der Doppelt verketteten Liste.

 

[alexschmid97]

ok, aber beim einfügen einer mittleren Stelle bei einer einfach verketteten Liste gilt schon O(n), da die Einfügeposition (Schleife ) berechnet werden muss oder ?

 

[alexschmid97]

und dann noch beim erweiten und anschließendem Einfügen:
Beim Array müsste doch dort zuerst überschrieben werden(erweitern) also ergibt sich ja O(n) . Bei der Liste bleibt die Komplexität ja eigentlich die selbe, da ja nur eine weitere Liste verknüpft wird oder?