ArrayInsert Worst Case

Bömmel
Neuling
Neuling
Beiträge: 4
Registriert: 7. Mai 2017 12:17

ArrayInsert Worst Case

Beitrag von Bömmel » 11. Jun 2017 10:40

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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: ArrayInsert Worst Case

Beitrag von LukasPhysiker » 11. Jun 2017 11:11

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
Neuling
Neuling
Beiträge: 7
Registriert: 19. Apr 2017 14:18

Re: ArrayInsert Worst Case

Beitrag von marvin » 11. Jun 2017 13:06

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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: ArrayInsert Worst Case

Beitrag von LukasPhysiker » 11. Jun 2017 13:16

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
Neuling
Neuling
Beiträge: 4
Registriert: 7. Mai 2017 12:17

Re: ArrayInsert Worst Case

Beitrag von Bömmel » 11. Jun 2017 14:37

vielen Dank für die schnellen und hilfreichen Antworten! :)

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: ArrayInsert Worst Case

Beitrag von invariant » 12. Jun 2017 13:33

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
Neuling
Neuling
Beiträge: 1
Registriert: 18. Mai 2017 19:20

Re: ArrayInsert Worst Case

Beitrag von hudikan » 14. Jun 2017 22:45

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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: ArrayInsert Worst Case

Beitrag von LukasPhysiker » 15. Jun 2017 00:07

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.

Antworten

Zurück zu „Archiv“