Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Rekursiver Durchlauf im Baum - Zeitkomplexität (http://www.informatikerboard.de/board/thread.php?threadid=2257)
Geschrieben von ubik am 07.05.2015 um 09:12:
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:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
|
algorithm SecondSmallestNumber (B)
{ Eingabe: B Wurzel des Baumes }
if B^.lTree != nil then
if B^.lTree^.lTree != nil then
return SecondSmallestNumber(B^.lTree);
else
return B^.key;
end if |
|
Und die Kostenfunktion:
| code: |
1:
2:
3:
4:
5:
|
1 + T(n), falls linkerTeilbaum^.linkerTeilbaum ungleich nil
T(n) =
1, sonst |
|
Wie kann ich daraus die Laufzeit berechnen, sodass O(log(n)) rauskommt?
Geschrieben von eulerscheZahl am 08.05.2015 um 15:44:
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).
Geschrieben von ubik am 09.05.2015 um 09:31:
Warum ist das eigentlich so, dass bei balancierten Bäumen Laufzeit O(log n) gilt und bei nicht balancierten Bäumen Laufzeit O(n)?
Geschrieben von eulerscheZahl am 09.05.2015 um 10:09:
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.
Geschrieben von ubik am 09.05.2015 um 10:26:
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!
Geschrieben von eulerscheZahl am 09.05.2015 um 10:38:
Wenn du nicht draufkommst, schau mal hier:
stackoverflow
Forensoftware: Burning Board, entwickelt von WoltLab GmbH