Seite 1 von 1

ArrayInsert Worst Case

Verfasst: 11. Jun 2017 10:40
von 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?
:|

Re: ArrayInsert Worst Case

Verfasst: 11. Jun 2017 11:11
von 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)).

Re: ArrayInsert Worst Case

Verfasst: 11. Jun 2017 13:06
von 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)

Re: ArrayInsert Worst Case

Verfasst: 11. Jun 2017 13:16
von 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.

Re: ArrayInsert Worst Case

Verfasst: 11. Jun 2017 14:37
von Bömmel
vielen Dank für die schnellen und hilfreichen Antworten! :)

Re: ArrayInsert Worst Case

Verfasst: 12. Jun 2017 13:33
von 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ß

Re: ArrayInsert Worst Case

Verfasst: 14. Jun 2017 22:45
von 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ß

Re: ArrayInsert Worst Case

Verfasst: 15. Jun 2017 00:07
von 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.