Formel in O-Notation < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:49 So 08.06.2008 | | Autor: | Tomiu |
| Aufgabe | | Beim Sortieren von n Zahlen durch "Diskretes Einfügen" gilt für die Anzahl [mm] v_{n} [/mm] der Vergleiche [mm] v_{1}=0 [/mm] und [mm] v_{n}=v{n-1}+n-1, [/mm] n=2,3,... und für die Zahl der Wertzuweisungen [mm] w_{1}=0 [/mm] und [mm] w_{n}=w{n-1}+n+1, [/mm] n=2,3,... Warum? Mann bestimme explizite Formeln für [mm] v_{n} [/mm] und [mm] w_{n} [/mm] und schätze deren Größenordnung (in der O-Notation) ab. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe folgende Formeln gefunden:
[mm] v_{n}=\bruch{n\*(n-1)}{2}
[/mm]
[mm] w_{n}=\summe_{i=3}^{n+1}i
[/mm]
Wie kann ich aber diese Formel in O-notation schreiben
Danke im voraus,
Tomiu
|
|
| |
|
> Beim Sortieren von n Zahlen durch "Diskretes Einfügen" gilt
> für die Anzahl [mm]v_{n}[/mm] der Vergleiche [mm]v_{1}=0[/mm] und
> [mm]v_{n}=v{n-1}+n-1,[/mm] n=2,3,... und für die Zahl der
> Wertzuweisungen [mm]w_{1}=0[/mm] und [mm]w_{n}=w{n-1}+n+1,[/mm] n=2,3,...
> Warum? Mann bestimme explizite Formeln für [mm]v_{n}[/mm] und [mm]w_{n}[/mm]
> und schätze deren Größenordnung (in der O-Notation) ab.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo,
>
> ich habe folgende Formeln gefunden:
>
> [mm]v_{n}=\bruch{n\*(n-1)}{2}[/mm]
>
>
> [mm]w_{n}=\summe_{i=3}^{n+1}i[/mm]
>
>
> Wie kann ich aber diese Formel in O-notation schreiben
Beide sind [mm] $\mathrm{O}(n^2)$. [/mm] Allgemein: ist [mm] $v_n$ [/mm] ein Polynom in $n$ vom Grade $k$, so ist [mm] $v_n=\mathrm{O}(n^k)$.
[/mm]
Um dies einzusehen, musst Du vielleicht die Definition von [mm] $\mathrm{O}$ [/mm] nochmals genauer anschauen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:23 Di 10.06.2008 | | Autor: | Tomiu |
Danke, Somebody
|
|
|
|
