# Löschen von Objekten bei Arrays



## ralph_1234 (6. Mai 2021)

Hallo, man hat ein Array A, welcher mit Werten befüllt ist und ein weiteres Array B mit aufsteigend sotierten Indizes. Jetzt muss man einen Algorithmus entwerfen, der die Werte von A löscht, an den Stellen von dem Array mit den Indizes. Das Problem ist, dass das alles in O(n) passieren muss. Die muss mit PseudoCode implementiert werden.
Meine Idee war es erstmal, alle Stellen des Arrays null zu setzen ( also nur die mit den Indizes aus B) und danach das Array "zusammenzudrücken", also dass keine null Werte mehr zwischen den anderen Werten liegen. Da liegt dann aber das Problem, dass ich mich dann in O(n²) befinde.


----------



## kneitzel (6. Mai 2021)

Wie kommst Du auf O(n²)?

Wenn Du eine Liste von m Indizes hast und n Elementen in der Liste (mit m < n), dann gehst Du einmal die Liste der Indizes durch und dann einmal das Array. Damit hast Du O(n+m) und da m <=n ist, wäre das somit O(2n) = O(n).

Somit wäre das durchaus in Ordnung. Wobei die Frage ist, ob man das Array beibehalten kann oder ob man ein neues Array erstellen muss. Aber das ist ein Detail, das Du aus der genauen Aufgabe ableiten musst.


----------



## Barista (7. Mai 2021)

Beim Zugriff auf das sortierte Array ist die Komplexität O(log2n).

Dazu kommt dann noch der direkte Array-Zugriff auf das zweite Array O(1).


Google Suche: O-Notation Komplexität für Zugriff auf sortiertes Array

Zeitkomplexit ̈at beim Suchen und Sortieren Thomas Schwotzer PDF


----------



## Barista (7. Mai 2021)

Für den Zugriff auf das sortierte Array: _java.util.Arrays.binarySearch_


----------



## kneitzel (7. Mai 2021)

Wo siehst du den Zugriff auf ein sortiertes Array?

Du hast nur normale Zugriffe auf einzelne Elemente des Arrays und die haben alle O(1).

Also musst Du nur schauen, was für Zugriffe Du genau hast:
Der erste Ablauf, den der TE haben wollte, war einmal das Zweite Array durchzugehen - das wäre dann O(m) wenn das Array Größe m hat. Für jedes erfolgt dann ein Zugriff auf das erste Array (Wert auf null setzen): O(1). ==> Das hat damit zusammen O(m)

Dann hast ein einfaches durchgehen des Arrays (Größe n) mit einzelnen Zugriffen. Im Worst Case hast Du diese Zugriffe:
- Lesen eines Elementes O(1)
- 2x Schreiben eines Elements was dann auch O(1) ist.

Damit hast Du zwei Dinge: O(m) + O(n)


----------



## Barista (7. Mai 2021)

kneitzel hat gesagt.:


> Wo siehst du den Zugriff auf ein sortiertes Array


Ach so, alle Werte Löschen, nicht bestimmte Werte anhand Indizes.


----------



## kneitzel (7. Mai 2021)

Ok, unglücklich formuliert: Wo siehst Du ein suchen in diesem sortieren Array?

Der TE hat ja schon ein Algorithmus skizziert der aus zwei Teilen bestehen würde. Dadurch das das zweite Array sortiert ist, kann man das alles in einem Schritt machen, denn das Löschen ist nicht notwendig (Wäre auch problematisch, wenn da ein null Wert nicht zugewiesen werden kann).

Aber an der Komplexität und möglichen Umsetzung in O(n) ändert sich nichts.


----------

