Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

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


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

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

Zitat:
Aber kann ich stattdessen nicht auch schreiben: O(3^logn) oder vielleicht O(3^(logn/log2))?


Wenn Du hier die Konstanten entfernst, so veränderst Du möglicherweise die Komplexitätsklasse in der Du bist. Das kann von "nach oben", also schlechte Abschätzung, bis "nach unten", also falsches Ergebnis, gehen.

Das ist so ähnlich, als wenn Du die Konstante 3 bei O(n^3) wegradizieren Würdest. Hier kannst Du nur nach oben abschätzen. D.h. O(n^4) usw., weil dadurch deine Abschätzung zunehmend schlechter wird. Wenn Du aber hingegen O(n^1) schreibst, so kann deine Matrixmultiplikation oder sonst noch was, schnell mit linearer Zeit gehen.

Im obigen Fall muss die Formel zuerst "per Hand" (nach oben) abschätzen und dann die Komplexitäten berechnen. In deiner Darstellung wird es relativ ecklig.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 28 Okt 2005 - 16:15:01    Titel:

Hi,

algebrafreak hat folgendes geschrieben:
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.


Ich versuch mal mein Glück:

Wenn man annimmt:

x^(log(3)/log(2))=3^(log(x)/log(2))

gilt (exponent von x links als logarithmus darstellen):

log(3)/log(2)=log(3^(log(x)/log(2)))/log(x)

weil gilt: log(a^b)=b*log(a), lässt sich das umschreiben zu:

log(3)/log(2)=log(x)/log(2)*log(3)/log(x), wobei log(x) sich rechts wegstreicht und
log(3)/log(2)=log(3)/log(2) übrigbleibt.

Abgesehen davon, dass das vielleicht kein mathematisch genügender Beweis ist, aber davon ausgehend, dass diese Beziehung gilt: Kann ich nun tatsächlich O(3^(log(n)/log(2))) schreiben?

Und wenn das tatsächlich gelten würde, wieso schreibt man es in der Literatur nicht so? Willkür? Weil es schöner aussieht?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 28 Okt 2005 - 16:21:01    Titel:

Ich schaue es mir mal an. Allgemein hat man "in der Literatur" eine große Angst vor Ausdrücken von der Form "3^f(x)", weil eben wenn f(x) >> log x liefert das eine sehr hohe Komplexität. Algorithmen mit einer solchen sind ineffizient. Ich habe auch als erstes auf den Exponenten geschaut und gemeint: Das geht doch nicht... Daher stellt man das lieber in einer polynomiellen Form, sofern es geht.
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
Seite 3 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