Rekursiver Durchlauf im Baum - Zeitkomplexität |
07.05.2015, 09:12 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Rekursiver Durchlauf im Baum - Zeitkomplexität Hallo, die Aufgabe lautete, man solle den zweitkleinsten Wert im Baum finden mit Laufzeit O(log(n)). Mein Algorithmus lautet:
Und die Kostenfunktion:
Wie kann ich daraus die Laufzeit berechnen, sodass O(log(n)) rauskommt? |
||||||||||
|
|||||||||||
08.05.2015, 15:44 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Der Algorithmus sieht gut aus. Die Laufzeit kriegst du über die Tiefe des Baums, die ja logarithmisch von der Anzahl der Werte abhängt (sofern der Baum balanciert ist). |
||||||||||
09.05.2015, 09:31 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Warum ist das eigentlich so, dass bei balancierten Bäumen Laufzeit O(log n) gilt und bei nicht balancierten Bäumen Laufzeit O(n)? |
||||||||||
09.05.2015, 10:09 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Ein nicht balancierter Baum ist im Extremfall einfach eine Liste. Und da brauchst du lineare Zeit zum Durchgehen. Ach ja: wenn der Wurzelknoten des Baums keinen linken, sondern nur einen rechten Kindknoten hat, findest du die zweitkleinste Zahl nicht. |
||||||||||
Anzeige | |||||||||||
|
|||||||||||
09.05.2015, 10:26 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Ja, das ist kein Problem. Die Aufgabenstellung lautete, einen balancierten Baum mit mindestens 4 Knoten nach der zweitkleinsten Zahl zu durchsuchen. Und ein balancierter Baum mit 4 Knoten hat immer einen linken Teilbaum von der Wurzel aus. Tja, jetzt frag ich mich nur noch, wie man die k-kleinste Zahl findet. Gar nicht so einfach! |
||||||||||
09.05.2015, 10:38 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Wenn du nicht draufkommst, schau mal hier: stackoverflow |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|