Aufwand von Algorithmus < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:35 So 09.09.2012 | | Autor: | Jack159 |
| Aufgabe | Gegeben sei ein Algorithmus A, dessen Aufwand p(n) ist, wobei p ein Polynom vom Grad k ist. Zeigen Sie, dass A den Aufwand [mm] O(n^k) [/mm] besitzt.
Hinweis: Falls nötig, Beispiele ausprobieren. |
Hallo,
Wir haben folgendes in der Vorlesung definiert:
(Mit O(...) ist das Laundau-Symbol gemeint)
Def.: Man sagt eine Folge [mm] (x_n) [/mm] ist O(f(n)): [mm] \gdw |x_n|\lec*f(n) [/mm] für schließlich alle n für eine konstante c.
Meine Lösung:
p ist also ein Polynom vom Grad k. Also wird p in etwa die folgende Gestalt haben:
[mm] p(x)=ax^k+bx^{k-1}+cx^{k-2}....
[/mm]
Uns intressiert hier nur [mm] ax^k. [/mm] Dies nun als Folge geschrieben:
[mm] x_n=a*n^k
[/mm]
Damit gilt doch:
[mm] |x_n| \le c*n^k \gdw a*n^k \le c*n^k [/mm] für schließlich alle n mit c [mm] \ge [/mm] a
Also gilt:
[mm] x_n=a*n^k [/mm] ist [mm] O(n^k)
[/mm]
Ist meine Lösung richtig?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:40 Mi 12.09.2012 | | Autor: | Marcel |
Hallo Jack,
> Gegeben sei ein Algorithmus A, dessen Aufwand p(n) ist,
> wobei p ein Polynom vom Grad k ist. Zeigen Sie, dass A den
> Aufwand [mm]O(n^k)[/mm] besitzt.
> Hinweis: Falls nötig, Beispiele ausprobieren.
> Hallo,
>
> Wir haben folgendes in der Vorlesung definiert:
>
> (Mit O(...) ist das Laundau-Symbol gemeint)
> Def.: Man sagt eine Folge [mm](x_n)[/mm] ist O(f(n)): [mm]\gdw |x_n|\le c*f(n)[/mm]
Du hattest dort ein Leerzeichen vergessen, deswegen sieht man
bei Dir nicht, was Du meinst!
> für schließlich alle n für eine konstante c.
>
> Meine Lösung:
>
> p ist also ein Polynom vom Grad k. Also wird p in etwa die
> folgende Gestalt haben:
>
> [mm]p(x)=ax^k+bx^{k-1}+cx^{k-2}....[/mm]
>
> Uns intressiert hier nur [mm]ax^k.[/mm] Dies nun als Folge
> geschrieben:
>
> [mm]x_n=a*n^k[/mm]
>
> Damit gilt doch:
>
> [mm]|x_n| \le c*n^k \gdw a*n^k \le c*n^k[/mm] für schließlich
> alle n mit c [mm]\ge[/mm] a
>
> Also gilt:
> [mm]x_n=a*n^k[/mm] ist [mm]O(n^k)[/mm]
>
>
>
> Ist meine Lösung richtig?
>
Nein, jedenfalls sehe ich das so, dass Du eigentlich das benutzt, was
Du zeigen sollst:
Nämlich dass für ein Polynom [mm] $p(x)=a_kx^k+a_{k-1}x^{k-1}+...+a_1x^1+a_0$ [/mm] gilt:
[mm] $$p(n)=O(n^k)\,.$$
[/mm]
(Ich weiß, unschöne, aber gängige Notation. Etwas besser
$$p(n) [mm] \in O(n^k)\,,$$
[/mm]
außerdem sollte da noch $n [mm] \to \infty$ [/mm] dabeistehen. Aber egal. Bei Dir
bzw. bei der Euch vorliegenden Definition ist übrigens [mm] $x_n=p(n)\,$ [/mm] für
alle [mm] $n\,$ [/mm] in der Aufgabe gemeint - das musst Du Dir erstmal klarmachen!)
Zu zeigen ist also:
Es gibt ein $c > [mm] 0\,,$ [/mm] so dass $p(n) [mm] \le c*n^k$ [/mm] für alle [mm] $n\,.$ [/mm] (Im Prinzip
bräuchte man auch nur alle [mm] $n\,$ [/mm] ab einem [mm] $n_0\,,$ [/mm] aber halten wir uns
an die von Dir zitierte Version).
(Das würde auch passen, wenn [mm] $p\,$ [/mm] einen Grad [mm] $\le [/mm] k$ hätte - bei
$> [mm] k\,$ [/mm] "wird die Aussage falsch"!)
Wie findet man sowas?
Nunja:
[mm] $$|p(n)|=\left|\sum_{m=0}^k a_m n^m\right| \le \sum_{m=0}^k |a_m| n^m \le (k+1)\underbrace{\max\{|a_0|,\;...,\;|a_k|\}}_{ \ge |a_k| > 0}\;\cdot n^k$$
[/mm]
Begründe diese Ungleichung für alle [mm] $n\,,$ [/mm] dann setze
[mm] $$c:=(k+1)\;\max\{|a_0|,\;...,\;|a_k|\}\,,$$
[/mm]
wobei der zweite Faktor wie oben angedeutet $> [mm] 0\,$ [/mm] ist, da [mm] $p\,$ [/mm] Grad
[mm] $k\,$ [/mm] hat!
Gruß,
Marcel
|
|
|
|
