Frage zu Sinn der Ober- unter-Schranke bei der O - Notation

[win8789]

Hallo,
Ich habe in meinen Lehrbuch einen Kapitel über die Θ- Notation gelesen. Hierbei gig es ja um eine eine Ober- und unter-Schranke, zwischen welcher die eigentlich Funtkion liegt z.b Θ(n²). Dabei wurde noch geschrieben. das die Ober- und untet-Schranke durch zwei Konstanten genbildet werden.
Nun frage ich mich: Warum muss man überhaut eine ober- und unter-Schranke bestimmen? Reicht die Angabe Θ(n²) nicht eigentlich aus? Oder hat die Ober und die Unter-Schranke etwas mit den anderen Teilen der Funtkion zu tuhen, welche man ja bei der Bestimmung der Θ-Notation wegläst?
z.B. an * bn²+ c = Θ(n²).

ps. Ich bin mir bewusst, dass im Title O-Natation steht und dies etwas anderes als die Θ- Notation ist. Aber das Zeichen Θ will nicht in der Titelzeile Funktionieren.

[SeppJ]

win8789 schrieb:

Warum muss man überhaut eine ober- und unter-Schranke bestimmen?

Wer ist "man" und warum denkst du, muss er das machen?

Reicht die Angabe Θ(n²) nicht eigentlich aus?

Ausreichend wofür?

Oder hat die Ober und die Unter-Schranke etwas mit den anderen Teilen der Funtkion zu tuhen, welche man ja bei der Bestimmung der Θ-Notation wegläst?

Ja, in gewisser Weise.

Bin gerade irgendwie etwas verwirrt. Offensichtlich hast du Θ-Notation verstanden, aber irgendwie auch nicht.
Bei diesen ganzen Komplexitätsklassen, egal in welcher Notation, interessiert man sich normalerweise nur dafür, wie die Laufzeit von der Eingabelänge n abhängt. Θ(n²) heißt, dass die Laufzeit quadratisch mit n zunimmt. Aber n² selber ist keine Laufzeit, es ist eine Zahl. (5 Sekunden)*n² ist eine Laufzeit. Aber kaum jemanden interessiert der genaue Vorfaktor.

[Jester]

Mir ist auch nicht so ganz klar was genau Dir fehlt. Die Angabe $f(n) \in \Theta(n^2)$ genügt natürlich insofern als dass das eine Angabe einer oberen und unteren Schranke ist. Das ist ja nur eine kurze Schreibweise für $f(n) \in O(n^2) \cap \Omega(n^2)$

[win8789]

Erst mal dir und jester danke für die Antwort.
Es geht halt darum, dass man erst sagt, dass man, der einfachhalthalber, die kleiner Teiler die Funtkion wegläst, um dann später diese bei den Schraken zu nehmen. Man hat eigentlich mit Θ(n²) (für insort-sort) den Worts-case ermittelt (gut nun kommt es noch auf die Tatsache an, wie lange ein Rechner bracht um das Ergebnis zu errechnen. Braucht man dafür die Schranken?).

Warum definiert man jetzt zwei schranken, die ab n0 gültig sind und zwischen welche die Funtkion liegt? Man kann ja vorallen die Schraken einigermassen locker definieren, solang n0 < n, c1ng < f(n) < c2ng; gilt.
Wieseo gibt man dann nicht direkt Θ(an²+bn-c) an? Wenn man a,b und c sowieso später für c1ng und c2ng braucht.

Im endeffekt, was will man mit der oberen und Unteren-Schrake ausdrücken?
Den rest glaube ich verstanden zu haben.

ps.

SeppJ schrieb:

Wer ist "man" und warum denkst du, muss er das machen?

Vorname: Jeder
Nachname: Man

[nachtfeuer]

Beispiele aus dem Alltag:

Wie lange braucht ein 3-Minuten Ei?

Wieviel Grundbegriffe kann man sich merken (eher statistisch?), wie viele in einer Klausur korrekt wiedergeben und wie viele braucht man zum Bestehen einer Prüfung - vorausgesetzt, andere Fragen werden mit der gleichen Antwortwahrscheinlichkeit bearbeitet.)

Analog dazu: Diablo2: wieviele Baalruns braucht man für Hell.

Abteilung Arbeitsfaul: wie viele Arbeitsschritte (z.B. Fahrradreifen flicken) muss ich mindestens ausführen?

Abteilung Lerneffient: wie viele Sortierverfahren muss ich mindestens anschauen, um den "höheren" "Sinn" einer unteren Schranke zu begreifen?

Abteilung KeineKohle: Wieviel Geld muss ich mindestens ausgeben, um a) Nicht zu verhungern/Mangelerscheinungen auszubilden und b) überdurchschnittlich gut (z.B. im Studium) zu performen?

Abteilung Statistik: ...ach ne, lieber nicht.

Abteilung LA: wieviele Formeln ...
(analog: wie viele Fumtionen?)

[Jester]

win8789 schrieb:

Warum definiert man jetzt zwei schranken, die ab n0 gültig sind und zwischen welche die Funtkion liegt? Man kann ja vorallen die Schraken einigermassen locker definieren, solang n0 < n, c1ng < f(n) < c2ng; gilt.
Wieseo gibt man dann nicht direkt Θ(an²+bn-c) an? Wenn man a,b und c sowieso später für c1ng und c2ng braucht.

Ich verstehe Dein Problem immer noch nicht. Warum sollte ich eine viel kompliziertere Formel hinschreiben, die dasselbe bedeutet? Der Clou an der O-Notation ist ja auch, dass die Koeffizienten eben nicht fest sind, sondern nur welche existieren müssen, sodass...

Aber offen gesagt ist mir immer noch nicht klar was Dein Problem ist. Mein Eindruck ist, dass Dir irgendwas zu kompliziert vorkommt und man es einfacher machen könnte. Was genau schwebt Dir da vor? Versuch doch mal ein ganz konkretes Beispiel zu machen.

@nachtfeuer: zu viel geraucht?

[win8789]

Mein Problem ist, dass ich nicht weiß, was man mir mit einer ober- unter-Schranke sagen will, wenn ich doch schon z.b Θ(n²) weiß.
Und was genau ist nun der Bereich zwischen den Schraken, welcher nicht auf f(n) liegt?

[Jester]

Was genau heißt für dich denn Theta(n^2)? Das ist doch per Definition nichts anderes als eine obere und eine untere Schranke.

Was ich bei Dir lese ist übersetzt also "was will man mir mit Theta(n^2) sagen wenn ich doch schon Theta(n^2) weiß" bzw. "was soll ich mit einer oberen und einer unteren Schranke, wenn ich doch schon eine obere und eine untere Schranke habe". vielleicht kannst du verstehen dass es mir schwer fällt dir da eine vernünftige hilfestellung zu geben.

[nachtfeuer]

win8789 schrieb:

Mein Problem ist, dass ich nicht weiß, was man mir mit einer ober- unter-Schranke sagen will, wenn ich doch schon z.b Θ(n²) weiß.
Und was genau ist nun der Bereich zwischen den Schraken, welcher nicht auf f(n) liegt?

Was liegt zwischen einem theoretisch formulierten Verfahren und seiner konkreten Ausgestaltung?

Die Betrachtung der oberen und unteren Schranken erlauben Vorhersagen und Einschätzungen. Ein Problem der Wahrnehmung ist, dass Algorithmen im mathematischen Sinne "effizent" (oder weniger "effizent") definiert werden.

Algorithmen in der Comuterwelt haben aber immer auch einen praktischen Bezug. Zeit spielt in der Mathematik so gut wie gar keine Rolle, in der Physik so lala (Für Licht gibt es ja keine "Zeit")(hat alle "Zeit" der Welt).

Um (aber) sinnvolle Vorhersagen zu machen (und um die Algorithmen selbst eventuell noch besser zu verstehen) kann man sich untere Schranken (oder bestimmte Elemente in der Elementmenge) und statistische Werte anschauen.

Eine Technik, die ganz gut zwischen reiner Berechnung/Mathe und konkreter Anwendung liegt, ist z.B. ein Entschlüsselungsprogramm.
Man könnte z.B. zur Passworterstellung die Rechenzeiten für Brute Force berücksichtigen - vorausgesetzt, die Rechner brauchen wirklich noch so lange, wie gedacht für Brute Force. Nun gibt es aber (auch noch...) verschiedene Erleichterungen wie z.B. Rainbowtables oder einfache Memories für besonders schwache Passwörter, welche die Rechenzeit verkürzen.
Statistiken helfen, den zu rechnenden Bereich einzugrenzen

Ein einfachreres Beispiel:
Cäsar-Verschlüsselung. Man muss den verschlüsselten Satz mit etwas Glück nur einmal rotieren. Jetzt lass dir von einem Freund einen von ihm geschriebenen Satz mit dem Cäsar-Verfahren verschlüsseln (Rotationstiefe unbekannt). Wie lange wirst du brauchen, um den Satz zu entschlüsseln?

[win8789]

nachtfeuer schrieb:

Die Betrachtung der oberen und unteren Schranken erlauben Vorhersagen und Einschätzungen. Ein Problem der Wahrnehmung ist, dass Algorithmen im mathematischen Sinne "effizent" (oder weniger "effizent") definiert werden.

Danke

Jester schrieb:

Was genau heißt für dich denn Theta(n^2)? Das ist doch per Definition nichts anderes als eine obere und eine untere Schranke.

Was ich bei Dir lese ist übersetzt also "was will man mir mit Theta(n^2) sagen wenn ich doch schon Theta(n^2) weiß" bzw. "was soll ich mit einer oberen und einer unteren Schranke, wenn ich doch schon eine obere und eine untere Schranke habe". vielleicht kannst du verstehen dass es mir schwer fällt dir da eine vernünftige hilfestellung zu geben.

Sry hab mich wohl etwas undeutlich ausgedrückt. ich meine warum muss ich eine obere und untere Schranke bestimmten, wenn ich doch schon die Komplexität der funktion f (n^2) weiß, welche zwischen den beiden konstant liegt. Mitlerweile glaube ich, dass es daubei darum geht eine breitere Einschätzung zu bekommen. Stimmt das?

[Jester]

Ich glaube so langsam sehe wo es hängt. Sehe ich es richtig, dass Dir unklar ist, warum Du Theta(n^2) schreiben sollst, wenn Du doch die Funktion f(n)=17 n^2 - 6n + 15 hast, und das ja viel präziser ist als das durch dermaßen unpräzise Schranken zu ersetzen?

Nun, der Grund ist der, dass man das (außer auf Übungsblättern) nicht macht. In den meisten Fällen kennt man die Funktion f nämlich nicht genau und ist daher auf die Abschätzung angewiesen. Wenn es einem gelingt die präzise Funktion aufzustellen, dann ist man natürlicn sofort fertig. Das gelingt aber nur in den seltensten Fällen, und dann muss man sich eben mit Schranken behelfen.

[win8789]

Jester schrieb:

Ich glaube so langsam sehe wo es hängt. Sehe ich es richtig, dass Dir unklar ist, warum Du Theta(n^2) schreiben sollst, wenn Du doch die Funktion f(n)=17 n^2 - 6n + 15 hast, und das ja viel präziser ist als das durch dermaßen unpräzise Schranken zu ersetzen?

Nun, der Grund ist der, dass man das (außer auf Übungsblättern) nicht macht. In den meisten Fällen kennt man die Funktion f nämlich nicht genau und ist daher auf die Abschätzung angewiesen. Wenn es einem gelingt die präzise Funktion aufzustellen, dann ist man natürlicn sofort fertig. Das gelingt aber nur in den seltensten Fällen, und dann muss man sich eben mit Schranken behelfen.

ja und die Tatsache, dass man bei der Θ-Natation zwar immer eine vereinfacht Form der Funtktion, welche die Laufzeit bestimmt, angibt, aber niemals den "Punkt" n0 oder die konstanten c1g(n) oder c2(n). Was eine geanauere Bestimmung der Schranken erschwärt.
Wenn man z.B nur n² weiß, anstatt f(n²), n0 = 2*max((|b|/a)) c1 = a/4, c2 7a/4.

p.s Im Buch steht zwar n0 = 2*max((|b|/a)), aber ich glaube, dass n0 = 2*max(|b|,a) mehr Sinn macht, oder?