ArrayInsert Worst Case

[Bömmel]

Hallo zusammen,
auf dem Übungsblatt beim Beispiel ArrayInsert ist uns nicht klar, wie der Worst Case zu wählen ist. Die längste Laufzeit des Algorithmus wäre ja, wenn man an Position 0 ein Element einfügen würde und an dieser Stelle sowie an allen anderen Stellen im Array kein null zu finden ist. Damit müssten alle Elemente um eine Position nach hinten verschoben werden. Dabei würden wir jedoch den Worst Case in Abhängigkeit von einer Eingabegröße wählen, nämlich der Position und dies ist laut dem Übungsplatt nicht gestattet ... Wie lautet der Worst Case richtig?

[LukasPhysiker]

Also, so wie ich mir das überlegt habe, hängt die Laufzeit ja einfach nur von der Differenz von der Einfügeposition n und der Länge des Arrays l ab. Dann muss man auch nicht mehr zwischen Best Case und Worst Case unterscheiden. Aber wenn n = l, ist die Komplexität natürlich 1 und nicht 0. n < l wäre schon außerhalb der Spezifikation und muss nicht betrachtet werden. Damit würde ich sagen ist die Komplexität Theta(max(1,n-l)).

[marvin]

Ich habe mir überlegt, dass im Best Case die Position des Arrays mit null belegt ist. Dann wäre die Komplexität für den Best Case konstant, weil das Element nur in das Array eingefügt wird. Also Theta(1). Der Worst Case wäre dann, wenn das Element an der Einfügeposition und alle Elemente nach der Einfügeposition ungleich null sind. Also ist der Worst Case abhängig von Einfügeposition und Listenlänge. Dann komme ich für den Worst Case auf die gleiche Komplexität wie LukasPhysiker. Theta(n-l)

[LukasPhysiker]

Ok, ich habe überhaupt nicht daran gedacht, dass ja mitten im Array schon die Position frei sein kann. Ich habe mir immer vorgestellt, dass erst am Ende des Arrays Positionen frei sind. In dem Fall hast du natürlich vollkommen Recht, es ist Theta(1) im Best Case und Theta(n-l) im Worst Case.

[Bömmel]

vielen Dank für die schnellen und hilfreichen Antworten!

[invariant]

Hallo,

die Lösungen klingen gut so. Aber am Besten immer noch definieren, was ihre Variablen beschreiben damit es nicht zu Verwirrung kommt.

Gruß

[hudikan]

Hallo,

dazu habe ich auch noch eine Frage.

Wenn, wie im zweiten Post erwähnt, die Einfügeposition n und die Länge des Arrays l ist, müsste dann im Worst Case die Komplexität nicht Omega(l-n) sein?
Angenommen ich habe ein Array der Länge 11 (Index 0 -9 belegt, 10 ist frei) und möchte jetzt an Index 0 Inhalt [A] mit [C] ersetzen. Dann muss ich doch alles ab Position 0 um eine Position nach rechts verschieben. Entspricht das nicht der Aussage (11-0) = 11, also (l-n)?
Also
[A][X][X][X][X][X][X][X][X][X][ ]

zu
[C][A][X][X][X][X][X][X][X][X][X]

Ich hoffe ich habe da jetzt keinen Denkfehler drin.

Gruß

[LukasPhysiker]

Haha, ja ich habe immer l-n gemeint, wenn ich n-l geschrieben habe. Sorry. n-l wäre ja negativ.

Aber wieso Omega statt Theta? Ich sehe nicht wie die Komplexität schlimmer werden könnte als l-n, also kann man ruhig Theta schreiben. Omega ist aber natürlich auch nicht falsch, da Theta ja O und Omega bedeutet.