Gilt die Groß-O Notation nur für Folgen?

[Nikolas]

Hallo

Ich habe gerade mit meinem Nebenfach Informatik begonnen und sitze nun an meinem ersten Übungszettel Info2 (Info 1 habe ich noch nicht gehört). Ich hänge gerade an der Aufgabe, eine Groß-O Notation für die Funktion n^5 zu zeigen. Meine Frage ist nun die: Ist dieses n eine natürliche Zahl (habe ich hier also ein Folge), oder kann ich das aus R nehmen und habe eine schöne Funktion auf dem R mit der ich ableiten kann?
Ich tippe mal auf n, da damit doch die Komplexität von Vorgängen beschrieben wird, die von der Anzahl der Parameter abhängt. (z.B. Anzahl der zu sortierenden Einträge) Aber als Physiker und Teilmathematiker kenne ich die passenden Konventionen nicht.

[3_of_8]

Ich schätze mal du meinst die Landau-Symbole, das große O ist ein großes Omikron und du sollst berechnen, wie schnell die Zeitfunktion zu einer gegebenen Funktion wächst.

Was n ist, weiß ich nicht. Aber ich vermute mal, es handelt sich um eine Zahl. Natürlich, ganz, rational, egal. Hauptsache, es lässt sich potenzieren.

n^5=n*n*n*n*n

Da sich die Anzahl der Faktoren nicht ändert, ist die Laufzeit der Funktion T=5 und es gilt T=5=O(1), die Funktion hat konstante Laufzeit.

[Nikolas]

Es geht um die untere Aufgabe. Die Definition habe ich aus einem anderen Skript entnommen. Im zweiten Fall müsste ich also das <= durch ein >= ersetzen. Im ersten Fall habe ich dann c=4 gesetzt und im zweiten dann c=1/2.

Wichtig war mit hauptsächlich, ob die ableiten oder vollständig induzieren darf. (brauch ich zwar beides hier nicht, aber vielleicht später mal)

[Nikolas]

Ich hätte direkt dazu noch eine Frage:

Das '=' (In Aufgabe 1) soll doch eher ein 'ist enthalten in' sein, oder? Links habe ich eine Funktion, rechts eine Menge. Wenn da wirklich ein = stehen würde, wäre ja die Kombination aus beiden Teilen die Aussage O(n^5)=Omega(n^5) was sicher falsch ist.

In der Aufgabe direkt darunter habe ich zwei Mengen zwischen denen ein '=' steht, mit dem Hinweis, dass hier nur eine Richtung zu zeigen ist, in dieser Aufgabe würde das Gleichheitszeichen nicht mathematisch korrekt benutzt werden. Der Zettel im Original

Könnte mir da jemand weiterhelfen?

[alcaeus]

Hallo,

bei den Landau-Symbolen hat es sich "eingebuergert", das Gleichheits- bzw. Ungleichheitszeichen fuer "ist Element von" bzw. "ist nicht Element von" zu verwenden.

Greetz
alcaeus

[3_of_8]

Das gehört so. Das = ist in diesem Fall eher ein "Element von"-Zeichen, aus a=O(n) und b=O(n) kann man auch nicht folgern, dass a und b die gleichen Funktionen sind, sondern nur, dass beide die gleiche Laufzeitkomplexität haben, nämlich lineare.

[alcaeus]

Zitat:

Zitat von 3_of_8

sondern nur, dass beide die gleiche Laufzeitkomplexität haben, nämlich lineare.

Falsch, nur dass sie langsamer oder hoechstens gleich schnell steigen wie O(n). Die Landausymbole werden fuer Angaben der Laufzeit- und Speicherkomplexitaet verwendet. Auf Funktionen angewandt (wie bei Nikolas der Fall) haben sie aber noch nichts mit Laufzeitkomplexitaet zu tun.

Greetz
alcaeus

[Nikolas]

Danke euch beiden. Ich werde in den nächsten Wochen wahrscheinlich noch ein paar Mal mit so Sachen ankommen :)

[Gausi]

Um nochmal zu der Anfangsfrage zu kommen, ob man in N oder R ist. Das ist eigentlich wurscht. In der Regel betrachtet man in der Informatik bei Laufzeit- und Platzbedarfabschätzungen Funktionen f:N -> N. Liegt ganz einfach daran, weil 7,543 Rechenoperationen nicht so oft vorkommen, und ein Speicherplatzbedarf von 3,543432 Byte macht auch keinen Sinn.

Man kann aber für die Argumentation ob "f = O(g)" durchaus erstmal annehmen, dass man Funktionen von R nach R hat, und Techniken aus der Analysis anwenden, um das zu zeigen oder zu widerlegen. Ob man nun so eine Treppenfunktion betrachtet, oder eine Kurve, die "glatt dadurch geht", ist für das Ergebnis nicht relevant. Aber meistens braucht man das nicht ;-).

Wenn man die Grundvorlesungen hinter sich hat, sind eh fast alle Algorithmen in O(N), NlogN und N^2. Und dann gibts natürlich die, die jenseits von Gut und Böse sind, also N!, 2^N und sowas. Aber da zeigt man dann nur noch, dass diese Probleme "NP-vollständig" sind und begnügt sich damit, dass man das nicht exakt in vernünftiger Zeit lösen kann ;-)

[3_of_8]

@alcaeus: Du hast natürlich Recht, ich bring das ständig durcheinander.

In DS I ist das bei mir immer so: Alle Operationen wie :=, +, -, *, /, and, or usw. brauchen genau eine Zeiteinheit. Das implizite Erhöhen der Schleifenvariable in einer for-Schleife wird nicht gezählt. Dadurch erhält man immer ganzzählige Ergebnisse für die Zeitfunktion eines Algorithmus und damit natürlich ein Element von N0.

Aber wenn man normalerweise das Wachstum einer Funktion betrachtet, können das auch rationale, reelle oder komplexe Zahlen sein.