Nr. 2
c)
FINDMISSING(A[1...n]) : int Missing
for i = 1 to n { //n Mal
copy A[i] -> B[1] //O(1) =: c1
C[B[1]] = 1 //O(1) =: c2
}
int answer;
for i = 0 to n { //n+1 Mal
if C[i] == NIL { //O(1) =: c3
answer = i; //O(1) =: c4 (wird genau einmal ausgefuehrt)
}
}
Obere Schranke fuer die Laufzeit ist also:
n*(c1 + c2) + (n+1)*c3 + c4 = n*(c1 + c2 + c3) + c3 + c4 = O(n)
Nr. 3
a)
Ganzheitsmethode
Wir bestimmen eine obere Schranke T(n) fuer die Gesamtkosten von n
Operationen.
Die Anzahl von Zweierpotenzen von i sei m und kann wie folgt berechnet
werden:
m = untereGaussKlammer(lg2(n))
T(n) = n - m + 2*(2^m - 1)
= n - m + 2^(m+1) - 2
Die armotisierten Kosten fuer eine Operation ergeben sich nun aus T(n)/n
T(n)/n = 1 + (2^(m+1) - m - 2) / n < 3 - (m + 2) / n < 3
Buchungsmethode
Wir setzen fuer jede Operation die Kosten auf 3. So koennen die Gesamtkosten
nach oben abgeschaetzt werden. Denn:
Induktion ueber die spezialelemente i = 2^m
Induktions Annahme fuer m = k gilt:
Kosten(2^k Operationen) < 3*2^k
Induktions Anfang (m = 1):
Reale Kosten(2^1 Operationen) = 1 + 2 = 3 < Amortisierte Kosten(2^1 Operationen) = 2*3 = 6
Induktions Schritt m = k + 1:
Reale Kosten(2^(k+1) Operationen) = Kosten(2^k Operationen) + 2^k - 1 + 2^(k+1) < 3*2^k + 2^k - 1 + 2^(k+1) =
6*2^k - 1 < 3*2^(k+1) = Amortisierte Kosten(2^(k+1) Operationen)
Diese Induktion beweisst die Gueltigkeit unserer Abschaetzung, jedoch nur fuer die Faelle das n eine Potenz von
2 ist. Dies ist jedoch keine Einschraenkung der Allgemeinheit, da die Realen Kosten der Operationen seit der
"letzen" Zweierpotenz 1 sind, und damit trivial kleiner 3.
b)
binaerZaehler b (auf dessen Binaerfeld wie auf ein Array mittels b[z] zugegriffen werden kann)
ZeigerAufGroesstes1-Bit z
INCREMENT
b = b + 1 //b wird in Gray-Code gespeichert => es wird nur ein Bit durch diese Operation geaendert
if b[z+1] == 1 {
z = z+1 //Das hoechstwertige 1-Bit hat sich um eine Stelle nach links verschoben
}
RESET
for i = 1 ... z
b[i] = 0
Offensichtlich ist Increment in O(1) da nur ein Bit geaendert wird
RESET haengt von Anzahl der vorangegangen INCREMENT Anweisungen seit
dem letzten RESET ab. Diese Anzahl sei m. Dann ist RESET offensichtlich
in O(log2(m)).
Amortisierte Analyse:
Wir veranschlagen die Kosten fuer RESET und INCREMENT fest auf 2. Das diese
moeglich ist sehen wir wenn wir daran, wenn wir ein RESET immer zusammen mit
allen seit dem letzten davorigem RESET angefallenen INCREMENT Operationen
betrachten. Solch ein "Block" hat nach obigen Ueberlegungen die Laufzeit
m + log2(m) < 2*m < 2*(m+1) //m+1 wegen des RESETs
Mit diesen Amortisierten Kosten ist also eine beliebige Folge von INCREMENT
und RESET Operationen in O(2*n) = O(n) moeglich
Nr. 4
a)
Vor[i] = -(Hoehe im Baum i)
Vor[j) = -(Hoehe im Baum j)
Algorithmus: UNION(i, j)
WENN |Vor[i]| < |Vor[j]|
Vor[i] <- j
SONST WENN |Vor[i]| > |Vor[j]|
Vor[j] <- i
SONST //|Vor[i]| == |Vor[j]|
Vor[i] <- j
Vor[j] <- Vor[j] - 1 //die Hoehe waechst um eins
b)
Ja