kulturfenster
Grünschnabel
Ich habe die Komplexität des folgenden Algorithmus zu bestimmen.
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!
Code:
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;
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!