Euklidischer Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:36 So 03.10.2010 | | Autor: | Papewaio |
| Aufgabe | | Die Laufzeit des Euklidischen Algorithmus ist [mm] \le [/mm] c*ln (min [mm] {n_{1},n_{2}}) [/mm] |
Mir ist der Euklidische Algorithmus klar, ich kann ihn auch beweisen. Bloß bei der Laufzeit fällt mir das schwer.
Mal der Ansatz:
Jede Zahl liegt zwischen zwei 2er Potenzen. [mm] 2^k \le [/mm] g < [mm] 2^{k+1}
[/mm]
Also:
k*log(2) [mm] \le [/mm] log g < (k+1) log(2)
Und weiter:
k [mm] \le [/mm] log(g)/log(2) < (k+1)
Durch die Annahme, dass die Zahl immer zwischen zwei 2er Potenzen liegt, ist mir klar, dass Halbierung folgen muss, wenn ich mit absolut kleinsten Resten rechne und bei positiv kleinsten Resten nach zwei Divisionsschritte. Aber wie schließt man genau daruaf, dass die Laufzeit [mm] \le [/mm] C*ln (min [mm] {n_{1},n_{2}}) [/mm] ist?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:54 Mo 04.10.2010 | | Autor: | felixf |
Moin!
> Die Laufzeit des Euklidischen Algorithmus ist [mm]\le[/mm] c*ln (min
> [mm]{n_{1},n_{2}})[/mm]
> Mir ist der Euklidische Algorithmus klar, ich kann ihn
> auch beweisen. Bloß bei der Laufzeit fällt mir das
> schwer.
> Mal der Ansatz:
> Jede Zahl liegt zwischen zwei 2er Potenzen. [mm]2^k \le[/mm] g <
> [mm]2^{k+1}[/mm]
> Also:
> k*log(2) [mm]\le[/mm] log g < (k+1) log(2)
>
> Und weiter:
> k [mm]\le[/mm] log(g)/log(2) < (k+1)
>
> Durch die Annahme, dass die Zahl immer zwischen zwei 2er
> Potenzen liegt, ist mir klar, dass Halbierung folgen muss,
> wenn ich mit absolut kleinsten Resten rechne und bei
> positiv kleinsten Resten nach zwei Divisionsschritte. Aber
> wie schließt man genau daruaf, dass die Laufzeit [mm]\le[/mm] C*ln
> (min [mm]{n_{1},n_{2}})[/mm] ist?
Du hast also einen Algorithmus in etwa wie folgt:
| 1: |
| | 2: | Solange BEDINGUNG(n, m)
| | 3: | ITERATION(n, m)
| | 4: | TAUSCHE(n, m)
| | 5: | Ende Solange
|
Du weisst, dass nach zwei Iterationen $n$ und $m$ sich mindestens halbiert haben, und die Bedingung ist erfuellt, solange $n$ und $m$ nicht zu klein werden.
Du sollst jetzt die Anzahl der Iterationen abschaetzen. Sei diese Zahl gleich $N$.
Schau dir jetzt folgende Variation des Algorithmus an:
| 1: |
| | 2: | Solange BEDINGUNG(n, m)
| | 3: | ITERATION(n, m)
| | 4: | TAUSCHE(n, m)
| | 5: | ITERATION(n, m)
| | 6: | TAUSCHE(n, m)
| | 7: | Ende Solange
|
Sei [mm] $N_1$ [/mm] die Anzahl dessen Iterationen. Es muss also $N [mm] \le [/mm] 2 [mm] N_1$ [/mm] gelten.
Diesen Algorithmus kannst du jetzt auch so formulieren, mit dem Wissen oben:
| 1: |
| | 2: | Solange BEDINGUNG(n, m)
| | 3: | Ersetze n durch etwas kleiner als n/2
| | 4: | Ersetze m durch etwas kleiner als m/2
| | 5: | Ende Solange
|
Dieser "Algorithmus" ist nicht langsamer als folgender:
| 1: |
| | 2: | Solange BEDINGUNG(n, m)
| | 3: | Ersetze n durch n/2
| | 4: | Ersetze m durch m/2
| | 5: | Ende Solange
|
Und dieser benoetigt hoechstens [mm] $\min\{ \log_2 n, \log_2 m \}$ [/mm] Schritte.
Also gilt $N [mm] \le [/mm] 2 [mm] N_1 \le [/mm] 2 [mm] \min\{ \log_2 n, \log_2 m \}$.
[/mm]
Das musst du jetzt noch etwas umschreiben (Monotonie des Logarithmus benutzen etc.), und beachten dass jede Iteration eine Laufzeit hat; dann hast du die Abschaetzung aus der Aufgabenstellung.
LG Felix
|
|
|
|
