maumau
unregistriert
 |
|
| Höhe von Rekursionsbäumen |
     |
Meine Frage:
Wie bestimme ich die Höhe eines Rekursionsbaumes?
Meine Ideen:
Bei Rekursionen wie die von Mergesort T(n) = 2T(n/2) + n ist die Höhe log_2(n) . Vermutlich wegen den rekursiven Aufrufen mit jeweils n/2 (?). Bei T(n) = 3T(n/4) + cn^2 ist die Höhe demnach log_4(n). Das das richtig ist, habe ich durch ein bisschen googlen herausgefunden. Aber wie ist die Höhe wenn T(n) = 3T(2n/3) + O(1) ist und wie bestimme ich diese? Hier kann man die Basis des Logarithmus nicht einfach aus dem rekursiven Aufruf ablesen.
|
|
02.04.2014 16:44 |
|
|
