Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Big-Oh Notation, Unklarheit
Gehe zu Seite Zurück  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 - 15:28:54    Titel:

Oh ich weiss die Antwort bereits. n^2 ist richtig, weil Durchschnitt von Best und Worst-Case.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 15:32:47    Titel:

algebrafreak hat folgendes geschrieben:
O(n log m + r)


:O Ich dachte, + kommt in O(...) niemals vor, weil die höhere Majorität im Grossen dominiert, hier also n*log(m)! Ist dem nicht so?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

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

Das Problem dabei ist, dass r grösser Werden kann als die n log n. Das ist eine krasse Nummer an sich. Es gibt höchstens n^2/4 Schnitte von senkrechten und waagerechten Linien in einem n/2 x n/2 Gitter. Und irgendwann mal wächst n^2/4 mehr als n log n (Anzahl der Zugriffe auf die Eingabe). Dann dominiert aber r die Komplexität. Das ganze nennt sich "Output-Sensitiv".
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 16:01:06    Titel:

Egal wie gross r ist, ist n*log(m) trotzdem dominant, auch wenn die beiden Zahlen seeeeehr gross dazu sein müssen Wink Aber ich seh was du meinst.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 27 Okt 2005 - 23:26:06    Titel:

Ich habe noch eine Frage, denn:

Ich habe für einen Algorithmus (Karatsuba-Multiplikation) folgendes Berechnet für die Anzahl benötigter Multiplikationen (mit n=Anzahl stellen der zwei natürlichen Zahlen):

f(n)=1/2*(3^(logn/log2-1/c+1)-3)

Der Literaturwert für die O-Notation ist O(3^(ln(3)/ln(2)), was ich nachvollziehen kann. Aber kann ich stattdessen nicht auch schreiben: O(3^logn) oder vielleicht O(3^(logn/log2))? Einfach den ausdruck oben so lassen und alle Konstanten löschen. Ich hab das Gefühl, ich kann es nicht, aber kannst Du es begründen? Very Happy
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 27 Okt 2005 - 23:36:15    Titel:

Das sieht irgendwie falsch aus. Die Komplexität ist ja O(n^(log irgendwas)) und nicht O(3^log(n irgendwas)). Also 3^log n darfst Du nicht nehmen, weil das, wie auch die andere Alternative, im Wesentlichen exponentiell ist.

Ich will Dir nichts vorschreiben, aber es gibt ein Standardwerkzeug, mit dem man solche Beweise führt. Das habe ich schon mal erwähnt. Das heißt "Master-Theorem". Darauf kann man sich schön beziehen und die Komplexität kommt direkt als Folgerung raus.

Es ist daher gar nicht nötig die exakte Zeit herzuleiten. Es ist sogar viel unsinniger, als Du denkst, denn, wie Du bereits gesagt hast, weißt Du nicht ob in deiner Implementierung Listen als Vektoren oder Arrays oder Hashes oder Heaps usw. implementiert sind.
BBB
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 28.10.2005
Beiträge: 303

BeitragVerfasst am: 28 Okt 2005 - 15:05:52    Titel:

Kann mir bei der Gelegenheit mal jemand erklären, wie man zeigen kann, dass für f(x)=x^(1/2) und g(x)=2^(ln(x)) f(x) in o(g(x)) ist?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 28 Okt 2005 - 15:27:50    Titel:

Du solltest ln zur Basis 2 darstellen und damit Anwendung von exp_2 eliminieren. Dann ist nicht mehr zu machen, als das in die Definition einzusetzen.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 28 Okt 2005 - 15:32:08    Titel:

algebrafreak hat folgendes geschrieben:
Das sieht irgendwie falsch aus. Die Komplexität ist ja O(n^(log irgendwas)) und nicht O(3^log(n irgendwas)).


Ich weiss dass es falsch aussieht und auch falsch ist, aber ich möchte wissen wieso.

3^log(x) ist ja bekanntlich dasselbe wie x^log(3), deshalb frage ich.

Zitat:

Ich will Dir nichts vorschreiben, aber es gibt ein Standardwerkzeug, mit dem man solche Beweise führt. Das habe ich schon mal erwähnt. Das heißt "Master-Theorem".


Ja, aber ich habe nicht die nötigen Grundlagen um das damit zu beweisen. Für mich ist es hingegen sehr einfach, die exakte Anzahl Multiplikationen zu berechnen und daraus auf O() zu schliessen (Konstanten etc weg).

Zitat:

Es ist daher gar nicht nötig die exakte Zeit herzuleiten. Es ist sogar viel unsinniger, als Du denkst, denn, wie Du bereits gesagt hast, weißt Du nicht ob in deiner Implementierung Listen als Vektoren oder Arrays oder Hashes oder Heaps usw. implementiert sind.


Ja, ich weiss dass ich die exakte Zeit so nicht berechnen kann und soll. Es ist aber dennoch ein einfacher Weg, O() zu berechnen. Und vergiss nicht: Ich schreibe diese Arbeit auf einem eher kleinem Niveau Wink Und die Herleitungen sind höchstens im Anhang, und da kann ich kaum mit dem Master-Theorem ankommen Wink

Gruss
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 28 Okt 2005 - 15:45:24    Titel:

Zitat:
3^log(x) ist ja bekanntlich dasselbe wie x^log(3), deshalb frage ich.


Na, wenn das so ist. Dann ist doch ja alles wunderbar. Der exponentielle Schein ist weg. Musst das halt nur beweisen, weil mir z.B. war das nicht bekannt. Und ich habe schon viel Scheiß gesehen.

Was das Master Theorem anbetrifft, so ist das Ding überhaupt nicht kompliziert. Ich empfehle es gerade deshalb, weil die Anwendung so kurz ist. Viel kürzer, als die Herleitung der Schritte, weil Du nur noch den Merge-Aufwand abzuschätzen brauchst. Auf der Wiki-Seite machen die es ja mit dem Master Theorem.
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 Zurück  1, 2, 3  Weiter
Seite 2 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