Laufzeit Algorithmus < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Berechnen Sie die Laufzeit des Algorithmus, ausgedrückt durch die Anzahl der durchzuführenden Multiplikationen in Abhängigkeit von n in den Spezialfällen [mm] $n=2^m$ [/mm] und [mm] $n=2^{m}-1$. [/mm] Überlegen sie, dass dies der schlechteste bzw. beste Fall ist.
Alogrithmus:
[mm] $x^n [/mm] = [mm] \begin{cases} 1, & \mbox{falls } n=0 \\ x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \mbox{falls } n \mbox{ ungerade} \\ x^{n-1} \cdot x, & \mbox{sonst} \end{cases} [/mm] |
Ich hab hier dann mal das hier rausgebracht:
erster Fall: keine Multikplation für beide Spezialfälle
zweiter Fall: [mm] ${x^2}^m$-Multikplikationen [/mm] für ersten Spezialfall und [mm] $x^{2^m-1}$-Multikplikationen [/mm] für zweiten Spezialfall
dritter Fall: [mm] ${x^2}^m$-Multikplikationen [/mm] für ersten Spezialfall und [mm] $x^{2^m-1}$-Multikplikationen [/mm] für zweiten Spezialfall
Ist das richtig?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Mi 27.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
