Löschen von Objekten bei Arrays

ralph_1234

Neues Mitglied
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.
 
K

kneitzel

Gast
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.
 
K

kneitzel

Gast
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)
 
K

kneitzel

Gast
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.
 

Neue Themen


Oben