Höhe von Rekursionsbäumen |
| 02.04.2014, 16:44 | Auf diesen Beitrag antworten » |
| maumau | 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. |
|
|
|
| 03.04.2014, 12:31 | Auf diesen Beitrag antworten » |
| maumau | 2n/3 = n/(1/2) -> Höhe des Baumes = log_(1/2)(n). Korrekt? |
|
|