Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
19.02.2009 Aufgabe 1
Sind meine antworten richtig?
bei a) hab ich falsch
b) 3
c) richtig
d) richtig
e) Bucketsort & Mergesort
f) 1
g) 1
h) 1
i) 1
meine Lösungen zu Aufgabe 1:
a) falsch
b) 3
c) richtig
d) richtig
e) bucket, merge
f) 1
g) bin ich mir nicht sicher und hätte gerne eine Erklärung dafür
h) bin ich mir nicht sicher und hätte gerne eine Erklärung dafür
i) 1
Ich würde sagen:
g) O(n² * log n)
Die erste Schleife läuft n-mal.
Die zweite Schleife läuft jeweils cn-mal.
Insgesamt also: n * cn * log n
h) O(n * (log n)²)
Die erste Schleife läuft n-mal.
Die zweite Schleife läuft jeweils log(cn)-mal.
Insgesamt also: n * log(cn) * log n.
Kann aber natürlich auch falsch sein, was ich mir da ausgedacht habe 
kann mir mal jemand die a) erklären 0o
Binärsuche funktioniert nur genau dann, wenn das Feld sortiert ist. Haldeneigenschaft ist keine Sortierung!
Hab ich auch (und hoffe das es stimmt).