Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Big-Oh Notation, Unklarheit
Gehe zu Seite 1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Big-Oh Notation, Unklarheit
 
Autor Nachricht
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 04:38:51    Titel: Big-Oh Notation, Unklarheit

Hallo,

Wie definiert man den Big-Oh Wert von 2*n-1/2? Wenn man die Regeln befolgt und alle Konstanten weglässt, kommt man auf O(n), nicht wahr? Da aber Big-Oh die Worst-Case Laufzeit definieren soll, passt das nicht so ganz, denn n ist immer kleiner als 2*n-1/2 für n>0.
Wie lautet also die richtige Big-Oh Notation von 2*n-1/2?

Das gleiche Problem stellt sich auch bei n^2+2*n (wo die O-Notation nach dem Majoritätsprinzip O(n^2) sein sollte, n^2 ist aber für n>0 immer kleiner als n^2+2*n).

Versteht jemand, was ich meine?

Gruss, Marko
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 12:48:28    Titel:

Erstens hast du bei de ganzen Geschichte das kleine "c" vergessen. Ein typischer Fehler. "f in O(g)" heißt:

es existiert ein c und ein n mit g(k) <= c * f(k) für alle k > n.

D.h. f ist ab einer (möglicherweise sehr großen) Zahlen k schließlich um ein multiplikatives konstantes Vielfaches größer als n.

Und zweitens heißt "f in O(g)" eigentlich "f ist eine Oberschranke von g". Also f ">" g in irgendeiner Hinsicht.

Bei f = 2n + 1/2 gilt f in O(n), denn für c = 1 und n = 0 gilt f(n) = 2n+1/2 > n. Aber auch umgekehrt ist n in O(2n + 1/2), denn für c = 3 z.B. und n = 1 gilt 3*k >= 2k+1/2 für alle k > n.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 13:48:53    Titel:

[quote="algebrafreak"]
es existiert ein c und ein n mit g(k) <= c * f(k) für alle k > n.
[quote]

g(k)=2k+1/2
c*f(k)=c*k
c*f(k)>g(k) für k>=0 ; c*k>2k+1/2

Soweit ich das überblicken kann gibt es kein k>k0>0, für das das immer gilt.

Zitat:

Bei f = 2n + 1/2 gilt f in O(n), denn für c = 1 und n = 0 gilt f(n) = 2n+1/2 > n.


Das versteh ich nicht. g ist doch meine tatsächliche Laufzeit (2n+1/2), nicht f, f ist die allg. Laufzeit (n). "2n+1/2 > n" liest sich wie "Die eigentliche Laufzeit ist grösser als die in Big-Oh notierte", was ja nicht sein kann, denn die in Big-oh notierte muss ja grösser sein, da es den Worst-Case darstellt.
f(n) ist schliesslich die 'abstrahierte' Laufzeit, ohne Konstanten. 2n+1/2 darf es also nicht sein.

Gruss
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 14:19:36    Titel:

Die O-Notation sagt für Funktionen f und g in der Selben Komplexitätsklasse nur aus, dass man durch Multiplikation eine zur Oberschranke von der anderen machen kann und zwar für schließlich alle n. Bei f(n) = 2n + 1/2 und g(n) = n (die in der selben Klasse "linear") liegen ist f(n) > g(n) ab n = 1 und 3g(n) > f(n) ab n = 1.

f in O(g)

sagt nicht unbedingt aus, dass g exakt oder immer kostengünstiger ist als f.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 14:52:29    Titel:

Hallo,

Machen wir das zum Verständnis an einem konkreten Beispiel durch:

Algorithmus, Eingabedan: Ein Array a mit n Elementen
Code:

for(int i=0;i<n-1;++i) {
TueDies(a[n]);
}
for(int i=0;i<n-1;++i) {
TueJenes(a[n]);
}



Mein Vorschlag:
Hier haben eine Laufzeit von g(n)=c1*n+c2*n=(c1+c2)*n=c*n. Es hat also eine Laufzeitkomplexität von f(n)=n, also schreibt man O(n).

Per Definition von Big-Oh soll ab n>n0 immer gelten: c*f(n)>g(n), also c*n>n.

Stimmt das so?



Wenn man den obigen Algorithmus vergleicht mit einem, der gleich ist, aber die zweite Schleife nicht hat, haben dennoch beide eine Laufzeitkomplexität von O(n), nicht wahr? Das heisst, man kann über Big-Oh hier nicht sagen, welcher Algorithmus schneller ist, obwohl der erste, weil er zwei Schleifen hat, länger dauert?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 15:18:53    Titel:

Zitat:
g(n)=c1*n+c2*n=(c1+c2)*n=c*n


Das hier ist die "exakte" Komplexität, wenn Du TueJenes und TueDies in c1 bzw. c2 Schritten durchführen kannst. Deine Funktion g ist dann in O(n). Und das heißt lediglich, dass die Laufzeit sich "in etwa" linear verhält. g ist aber auch in O(1) z.B. g läuft also länger oder gleich schnell als konstant bzw. als linear. g ist aber nich in O(n^2). D.h. quadratische Funktionen laufen länger als g.

Zitat:
Wenn man den obigen Algorithmus vergleicht mit einem, der gleich ist, aber die zweite Schleife nicht hat, haben dennoch beide eine Laufzeitkomplexität von O(n), nicht wahr? Das heisst, man kann über Big-Oh hier nicht sagen, welcher Algorithmus schneller ist, obwohl der erste, weil er zwei Schleifen hat, länger dauert?


Genau. Die laufen beide in etwa linear ab. g in O(n) bedeutet hier, dass g nicht wesentlich länger braucht als jede andere lineare Funktion.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 15:20:38    Titel:

Juhuu ich hab die Notation endlich begriffen Very Happy Danke!
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 15:23:42    Titel:

Oh, noch etwas Kleines: Darf man in O(...) mehr als eine Variable benutzen?

Eine Multiplication von zwei Ints mit den Längen n und m dauert ja g(n,m)=n*m. Darf ich O(n*m) notieren oder muss es O(n^2) sein?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 15:28:37    Titel:

Ja. Man darf sogar die Länge der Ausgabe einbeziehen! Z.B. die Konstruktion von Linienschnitten senkrechter und Waagerechter linien geht in O(n log m + r), wobei r die Anzahl der Elemente in der Ausgabe ist und n die Anzahl der senkrechten z.B. Kanten und m der waagerechten.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 25 Okt 2005 - 20:59:13    Titel:

Zitat:
es existiert ein c und ein n mit g(k) <= c * f(k) für alle k > n.


Mir ist beim Nachdenken eingefallen, dass ich mich hier vertan habe. Es heißt natürlich f in O(g)

es existiert ein c und ein n mit f(k) <= c * g(k) für alle k > n.

Heißt: f ist nicht wesentlich größer bzw. schneller als g. Der Rest (Intuition) ist trotzdem richtig. Kommt davon, dass man auswendig schreibt ohne nachzudenken.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Big-Oh Notation, Unklarheit
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2, 3  Weiter
Seite 1 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum