Ich habe die Komplexität des folgenden Algorithmus zu bestimmen.

Code :

1 2 3 4 5 6 7 8 9

INPUT: A Sequence A of n integers between 0 and n OUTPUT: A Sequence B of n integers Let B be a new Sequence containing n zeros.   while (! A.isEmpty() ) {     i = A.remove(A.first());     B.replaceAtRank(i, B.elementAtRank(i) + 1)   } return B;

Nun gilt es zu unterscheiden, ob die Sequenzen als Array oder Doubly Linked List implementiert wurden.

Hier was ich mich überlegt habe: Bitte um Korrektur!
die while-Schlaufe wird n mal durchlaufen, also bis A null ist. Die erste Anweisung ist konstant, also O(1). Die 2. hängt davon ab, ob die Sequenz als Array oder Linked List implementiert wurde. richtig?
Wie sich dieser Unterschied bemerkbar macht, bleibt mir leider ein Rätsel. Klar ist, dass bei hohem "i" die Doubly Linked List von hinten durchgeht. Doch wie macht sich das bemerkbar?

Selbstverständlich erwarte ich nun keine Lösung! Wenn mir aber jemand einen Ratschlag geben könnte, wäre mir sehr geholfen! Vielen Dank!

Hi,
also da man nicht genau weis an welcher Stelle das zu ersetzende Element steht würde ich vom Worst Case ausgehen. Wenn die DoubleLinkedList so implementiert ist das sie sie von hinten sucht ist der
Aufwand an dieser Stelle n/2. Da aber zwei Funktionen aufgerufen werden
elementAtRank und replaceAtRank hast du eine Komplexität von n. Das macht
zusammen mit der Komplexität der Schleife die, wie du schon richtig erkannt hast n ist, eine Komplexität von n². Im best Case hast du eine Array an dieser Stelle und damit eine Komplexität von n.

Was gibt die remove Funktion denn eigentlich zurück ?

Gruß Benny

Vielen Dank für die Antwort!

Die removeFunktion gibt, wenn ich das richtig verstanden habe, das 1. Element der Sequenz A zurück. Wahrscheinlich meinst du aber etwas anderes, denn das liegt glaub auf der Hand

Was ich aber noch nicht verstehe, ist wieso der Array eine bessere Laufzeit besitzt. Dass man eine DoublyLinkedList auch von hinten durchgehen kann, soll doch der Laufzeit dienen?

Gesucht ist in der Aufgabe jeweils der WorstCase. Einer für eine Implementierung mit einem Array, einer mit einer DoublyLinked list.

Zitat von kulturfenster

Vielen Dank für die Antwort!

Die removeFunktion gibt, wenn ich das richtig verstanden habe, das 1. Element der Sequenz A zurück. Wahrscheinlich meinst du aber etwas anderes, denn das liegt glaub auf der Hand

Die first() Funktion gibt das erste Element zurück
Wenn die remove() Funktion das Element zurück gibt was gelöscht wurde
hasst du in diesem Fall recht.


Hier mal eine Beispielaufbau einer DoubleLinkedList.
Die Elemente stehen in der Reihenfolge untereinander wie sie
verkettet sind. Das Valuefeld hab ich weggelassen.
In a steht immer die Referenz (Adresse) des aktuellen Knoten.
n steht für next und p für previous.


head(x1);
tail(x3);
lenght(5);

0 a(x1):{p(0);n(x9)}
1 a(x9):{p(x1);n(x4)}
2 a(x4):{p(x9);n(x6)}
3 a(x6):{p(x4);n(x3)}
4 a(x3):{p(x6);n(0)}

Wenn jetzt die elementAtRank() Funktion mit dem Parameter 2
aufgerufen wird dann wird warscheinlich folgendes passieren:

Code :

1 2 3 4 5 6 7 8 9

int range = length/2; //range(2) in range sollte jetzt eine 2 stehn   if( parameter >= range ){    //Es wird eine Funktion aufgerufen die das Element von hinten sucht.    return getElementByTailAtRank( parameter ); }else{    return getElementByHeadAtRank( parameter );     }

Und so könnte dann der Aufbau der getElementByTailAtRank() fuktion aussehn:

Code :

1 2 3 4 5 6 7 8

int i = length; node p = tail;   while( true ){ if( i = parameter )return p.getValue(); p = p.getPrev(); i--; }

Um jetzt also an das Elemant am Rang 2 ran zu kommen wird die
Schleife 3 mal durchlaufen. Wobei beim 3. Durchlauf das ifstatement
true wird und ein return erfolgt.
Bei n Elementen in dieser Liste ist die Komplexität also n/2 aufgerundet
Bei der replaceAtRank() Funktion ist es genau gleich. Du hast mit
diesen beiden Aufrufen eine Komplexität von n. Bei ungeradem n sogar eine
Komplexität von n + 1 da du ja im Worst Case 2 mal um 0.5 aufrundest


Wenn die Implementierung mit einem einfachen Feld gemacht ist sieht
das natürlich anderst aus. Gehn wir davon aus das das Feld wie das
folgende aussieht:

list(x4)
length(5)

0 a(x4){v(0)}
1 a(x5){v(0)}
2 a(x6){v(0)}
3 a(x7){v(0)}
4 a(x8){v(0)}

v steht hier für den Value an der jeweiligen Stelle. Ich geh der einfachheit
halber mal davon aus das ein Integer ein Speicherblock groß ist.
Was dir sicher schon aufgefallen ist das hier die Speicheradressen am Stück
vorhanden sind. Erfolgt jetzt wieder der aufruf der Funktion elementAtRank()
mit dem Parameter 2 passiert folgendes:

Code :

1	return list[2];

Bei der Zugriffsoperation mit den Klammern [] wird die startadresse des
Feldes x4 genommen und 2 drauf addiert. Also gibt es einen Zugriff auf die
Speicherstelle x6 und da haben wir unseren Rang 2. Der zugriff ist
egal für welchen Parameter also konstant also O(1)!

Gruß Benny

Hallo,

ich kenne mich zwar mit Komplexitätrechnung nicht aus, hätte aber trotzdem einen Einwand zu der hier festgestellten n² Klasse.
In diesem Stück Code wird, wie ich das sehe immer das 1. Element des Containers gelöscht. Damit ist imo der Aufwand für beide Operationen innerhalb der Schleife, unabhängig davon ob es sich um eine DoubleLinkedList oder ein Array handelt, konstant:
1.) Wird immer das erste Element gelöscht.
2.) Wird in Liste B immer das 2 Element mit dem 3. Element der Liste B ersetzt.

Somit gilt "Bestcase = Worstcase = O(n)". Oder sehe ich das falsch?

Gruß,
RedWing

Hm also das +1 hab ich noch übersehn aber das sollte glaub ich nicht viel ändern an meiner Theorie. Die remove und die first Funktion sind in jedem
Fall Konstant. Zumindest in dieser Konstilation.

2.) Wird in Liste B immer das 2 Element mit dem 3. Element der Liste B ersetzt.

Wie kommst du da drauf das das zweite Element mit dem dritten ersetzt wird?
Wenn remove den entfernten Wert zurückliefert kann da ja auch ne 4 drin stehen. Dann steigt die Komplexität wie oben beschrieben. Auser remove gibt die Position des Elements zurück das entfernt wurde, dann hast du Recht.

Benny

Hi.

Zitat von RedWing

Hallo,

ich kenne mich zwar mit Komplexitätrechnung nicht aus, hätte aber trotzdem einen Einwand zu der hier festgestellten n² Klasse.
In diesem Stück Code wird, wie ich das sehe immer das 1. Element des Containers gelöscht. Damit ist imo der Aufwand für beide Operationen innerhalb der Schleife, unabhängig davon ob es sich um eine DoubleLinkedList oder ein Array handelt, konstant:
1.) Wird immer das erste Element gelöscht.
2.) Wird in Liste B immer das 2 Element mit dem 3. Element der Liste B ersetzt.

Somit gilt "Bestcase = Worstcase = O(n)". Oder sehe ich das falsch?

Ja, das hast du etwas missverstanden.

Zuerst wird die Schleife n-mal durchlaufen - das ist klar.

Die erste Anweisung entfernt das erste Element aus der Sequenz. Das Finden des ersten Elements ist für Array und DList gleich: O(1). Das Löschen eines Elementes am Anfang des Arrays erfordert allerdings ein Verschieben aller Arrayelemente um 1 Position => O(A.n-1) - bei der DList ist die Komplexität der Operation konstant: O(1).

Die Funktion remove gibt das entfernte Element zurück. Der Algorithmus vermerkt also in der Sequenz B wie oft ein Element der Sequenz A aufgetreten ist. Allerdings ist da noch ein Off-By-One Error drin - die Sequenz B müßte n+1 Elemente groß sein, denn alle Elemente von A liegen ja zwischen 0 und n.

Bei den Funktionen replaceAtRank und elementAtRank ist das Array wieder deutlich im Vorteil. Der Zugriff und auch das Speichern eines Elementes ist konstant - O(1).

Wie kle-ben schon sagte, falls die DList vor- und rückwärts durchlaufen werden kann ist die Komplexität zum Aufsuchen eines Elements max. O(B.n/2). Dazu kommt nochmal das Aufsuchen der richtigen Stelle zum Speichern des Wertes. Was allerdings nicht zum Tragen kommt, wenn die DList einen Cursor verwendet - das hängt eben von der Implementierung ab.

Also, für das Array: O( [ (n - 1) * n / 2 ] + n ) = O( (n² + n) / 2 ) = O( n² ).
Für die DList mit Cursor: O( n + n² / 2 ) = O( n² ).

Für den verwendeten Algorithmus nehmen sich beide Implementierungen nichts. Das Array ist durch das Löschen, die DList durch den Zugriff ungünstig.

Gruß

An das Umschieben im Feld hab ich garnicht gedacht.
Allerdings hängt das auch wieder von der implementierung ab.
Wenn der Zugriff auf das Feld optimiert ist wird vieleicht nur der
Startindex intern verschoben wenn die Randelemente des Feldes
gelöscht werden. Man müsste denke ich die Implementierung kennen
um es genau sagen zu können.

Benny

Oh natürlich! Hab da wohl so einiges überlesen
Danke euch für die Erklärung ...

jep, ich danke auch!!