Rekurrenzgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:35 So 27.03.2005 | | Autor: | Tyvan |
Hallo,
kurze Frage.
Ich habe noch einige Mängel bei der Bestimmung der Rekurrenzgleichung anhand von vorgebenem Programmcode.
Ich weiss nicht so recht welche Komplexität welcher Programmcode hat.
Dabei ist die Gleichung immer als T(n) zu bestimmen.
Habe erst vor kurzem gelesen das z.B. [mm] T(\bruch{n}{3}) [/mm] genau [mm] O(log_{3}n) [/mm] entpsricht. Kennt einer vielleicht eine gute Seite über Rekurrenzgleichungen. Oder hat jemand Ahnung.
Dank im voraus.
|
|
| |
|
Hallo Tyvan!
> Ich habe noch einige Mängel bei der Bestimmung der
> Rekurrenzgleichung anhand von vorgebenem Programmcode.
>
> Ich weiss nicht so recht welche Komplexität welcher
> Programmcode hat.
> Dabei ist die Gleichung immer als T(n) zu bestimmen.
>
> Habe erst vor kurzem gelesen das z.B. [mm]T(\bruch{n}{3})[/mm] genau
> [mm]O(log_{3}n)[/mm] entpsricht. Kennt einer vielleicht eine gute
> Seite über Rekurrenzgleichungen. Oder hat jemand Ahnung.
Du könntest ja mal im Internet unter den Stichwörtern "Rekurrenzrelation" und "Master-Methode" bzw. "Master-Theorem" suchen. Ich habe da ziemlich gute Treffer erhalten. Schau auch mal ![[]](/images/popup.gif) hier, oder in diversen Büchern wie z.B. "Cormen/Leiserson/Rivest/Stein - Algorithmen eine Einführung".
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
|
