O Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo! Ich habe irgendwie diese O Notation noch nicht wirklich verstanden!
Hier meine frage:
Ich soll Funktionen mit hilfe der O Notation vereinfachen.
Wenn ich jetzt z.B: T1(n) = 2n+5 habe ist das O(n) weil der Grenzwert 2 ist???
Oder weil ich alles bis auf n einfach weglassen kann?
bei T2(n) = k1 [mm] n^2-8 [/mm] = [mm] O(n^2) [/mm] ist es ja auch das [mm] n^2.
[/mm]
Genau verstehe ich das nicht.
bei T3(n) = k2 n log n + k3 = O(n log n)
kann mir das mal jemand am Beispiel T3 und bitte an T3(n)+T2(n) und
T3(n)*T2(n) genau erläutern?
Ich komm einfach nicht weiter!!!
Danke,
NIK
|
|
| |
|
Hallo Nik!
Vielleicht hilft dir das hier weiter: ![[guckstduhier]](/images/smileys/guckstduhier.gif "[guckstduhier]")
> Hallo! Ich habe irgendwie diese O Notation noch nicht
> wirklich verstanden!
>
> Hier meine frage:
>
> Ich soll Funktionen mit hilfe der O Notation vereinfachen.
>
> Wenn ich jetzt z.B: T1(n) = 2n+5 habe ist das O(n) weil
> der Grenzwert 2 ist???
> Oder weil ich alles bis auf n einfach weglassen kann?
Ich würde das mit Worten so erklären, dass du die Funktion durch eine lineare Funktion (es ist ja O(n)) nach oben hin beschränken kannst.
> bei T2(n) = k1 [mm]n^2-8[/mm] = [mm]O(n^2)[/mm] ist es ja auch das [mm]n^2.[/mm]
>
> Genau verstehe ich das nicht.
>
> bei T3(n) = k2 n log n + k3 = O(n log n)
>
> kann mir das mal jemand am Beispiel T3 und bitte an
> T3(n)+T2(n) und
> T3(n)*T2(n) genau erläutern?
Ich hab auch lange gebracht, bis ich das verstanden habe und bin mir nicht sicher, ob ich wirklich alles verstanden habe. Aber im Prinzip gibt es so ein paar "Beschränkungsklasse", eben z. B. O(n), [mm] O(n^2), [/mm] natürlich auch alle [mm] O(n^3), O(n^{irgendwas}), [/mm] aber eben auch O(log n), O(n log n), ich glaub', das sind die wichtigsten. In der Regel sucht man die kleinste Schranke für eine Funkion, und soweit ich weiß ist log n die beste Schranke, also wenn man einen Algorithmus hat, dessen Laufzeit dadurch beschränkt wird, dann ist das deutlich besser, als wenn sie nur durch n beschränkt wird.
Grob gesagt musst du bei solchen Aufgaben als Schranke immer den größten Term deiner Aufgabe nehmen. Wenn du also hättest log n+n dann könntest du das durch n beschränken, denn log n ist "kleiner" als n und n alleine wird auch durch n beschränkt.
Ich hoffe, ich konnte dir ein bisschen helfen - vielleicht hilft's auch, wenn du dir viele Aufgaben anguckst...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:06 Di 05.04.2005 | | Autor: | Flugzwerg |
Hallo Bastiane!
Danke für Deine schnelle Antwort, so ähnlich habe ich es mir auch gedacht, war aber noch arg unsicher.
Zumindest konnte ich jetzt schon alte Einsendeaufgaben schon mal ganz gut lösen.
Musste lachen als ich den Thread gelesen habe den Du mir angegeben hast!
Mit dem Programmieren habe ich nämlich auch so meine Schwirigkeiten! Aber wer fleissig übt... 
VG,
NIK
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:04 Do 07.04.2005 | | Autor: | bazzzty |
Vielleicht noch mal eine kleine Zusammenfassung der [mm]\mathcal{O}[/mm]-Notation.
Für eine Funktion [mm]f(n)[/mm] ist [mm]\mathcal{O}(f)[/mm] definiert als die Menge aller Funktionen [mm]g[/mm], für die es eine Konstante [mm]c[/mm] gibt, so daß ab einem [mm]n_0[/mm] gilt, daß [mm]g(n)\leq c\cdot f(n)[/mm], also
[mm]\mathcal{O}(f)=\{g\mid \exists c,n_0 \forall n\geq n_0: g(n)\leq cf(n)\}[/mm]
Mit anderen Worten: Die Menge [mm]\mathcal{O}(f)[/mm] beinhaltet all die Funktionen, die sich durch ein konstant skaliertes [mm]f[/mm] beschränken lassen. Insofern wäre eigentlich korrekter, zu schreiben [mm]g\in\mathcal{O}(f)[/mm], aber das wird uneinheitlich gehandhabt.
Wenn man diese Definitionen im Kopf hat, dann muß man nicht mehr mutmaßen, sondern kann die Zuordnungen auch ganz leicht beweisen. Dabei versucht man immer, einen prägnanten, möglichst einschränkenden Term zu finden, d.h. Es ist zwar [mm]n+n\log n+3^2\in \mathcal{O}(n^2)[/mm], aber das schränkt nicht besonders eng ein, andererseits ist [mm]n+n\log n+3^2\in \mathcal{O}(12\cdot n\log n+23)[/mm], und das ist auch 'einschränkend' in dem Sinne, daß auch [mm]12\cdot n\log n+23\in \mathcal{O}(n+n\log n+3^2)[/mm] liegt, aber besonders prägnant ist es eben nicht.
Zu deinen Aufgaben (die Du ja wohl schon raushast, aber eben mehr mit Hingucken):
[mm]T_1=2n+5=\mathcal{O}(n)[/mm], weil [mm]\forall n\geq 3:2n+5\leq 3n[/mm] ([mm]n_0=3, c=3[/mm], zum Beispiel)
[mm]T_2=k_1n^2-8=\mathcal{O}(n)[/mm], weil [mm]\forall n:k_1n^2-8\leq k_1n^2[/mm] ([mm]n_0=0, c=k_1[/mm], wieder nicht als einzige Möglichkeit)
[mm]k_2 n \log n + k_3=\mathcal{O}(n\log n)[/mm], weil [mm]\forall n\geq 1: (k_2+k_3) n\log n[/mm] ([mm]n_0=1, c=k_2+k_3[/mm])
So, jetzt suchst Du für
[mm]T_4=T_2+T_3[/mm] und für [mm]T_5=T_2\cdot T_3[/mm] noch Abschätzungen. Und da hilft Dir etwas, daß Du Dir jetzt leicht selbst überlegen kannst:
Ist [mm]T_1 \in \mathcal{O}(f_1)[/mm] und [mm]T_2 \in \mathcal{O}(f_2)[/mm], dann ist [mm]T_1+T_2[/mm] in [mm]\mathcal{O}(f_1+f_2)[/mm]
[mm]T_1\cdot T_2[/mm] ist in jedem Fall in [mm]\mathcal{O}(f_1\cdot f_2)[/mm]. Beide Ergebnisse lassen sich gegebenenfalls noch verbessern, indem man eine Funktion [mm]f_3[/mm] findet, so daß [mm]f_1+f_2\in \mathcal{O}(f_3)[/mm] bzw. [mm]f_1\cdot f_2\in \mathcal{O}(f_3)[/mm]. Tipp: Im [mm]\mathcal{O}[/mm]-Kalkül sind Summen nie nötig, d.h. [mm]f_1+f_2\in \mathcal{O}(f_1)[/mm] oder [mm]f_1+f_2\in \mathcal{O}(f_2)[/mm] (warum?).
|
|
|
|
