o-notation?

[sankafahrer]

Hallo zusammen,

ich habe gerade mit dem Informatikstudium begonnen und stehe vor der Aufgabe auf die Frage:

Warum sagt die Behauptung „Die Laufzeit von Algorithmus A ist mindestens

O(n2)“ nichts aus?

eine sinnvolle Antwort zu finden.

Ich dachte eigentlich, dass ich die O-Notation so weit verstanden habe, aber irgendwie verwirrt mich diese Frage.

Meine erster Lösungsgedanke war, dass es sich bei O-Notationen immer um obere Schranken von Laufzeiten handelt, also keine Aussage über die Mindestlaufzeit getroffen wird.

Bin ich da auf dem richtigen Weg?

Vielen Dank schon mal für eure Hilfe!

Gruß

Andy

[Guybrush Threepwood]

Meine erster Lösungsgedanke war, dass es sich bei O-Notationen immer um obere Schranken von Laufzeiten handelt, also keine Aussage über die Mindestlaufzeit getroffen wird.

Ja genau das hab ich mir auch gedacht als ich die Frage gelesen habe.

[chrisLB]

Naja du hast es doch richtig gesagt, die Groß-O-Notation gibt die obere Schranke der Laufzeit an, wenn man dann von mindestens redet, kann diese ja sonst wie groß sein also zB n^99999999.. Und ja was hat man von dieser Aussage.

Grüße Chris

[sankafahrer]

Vielen Dank! Das hat mir sehr geholfen!

Gruß

Andy

[Rock_Bottom]

Hallo,

ich bin erst 16 und bin wohl noch nicht so weit wie die meisten hier, aber ich hätte dennoch gerne eine Frage.

Ich verstehe zwar die O Notation (wie man es nimmt), aber ich habe gewisse Probleme beim Beweisen.

Als Beispiel:

Es wird gefragt ob

i) Summe (2i+1) = O(n²) ist

Nach Umformen würde für mich folgendes herauskommen

2*( (n (n+1) ) / 2) + n = n² +2n <= c * n²

woraus folgt c>= 1 + (2/n) ----> c = 3

So weit so gut.

Bei

ii) (n+1)! = O(n!)

hätte ich es wie folgt gemacht

(n+1)! = n! (n+1) <= c * n!

(n+1) <= c

Bis hier hin. Mein Beweis wäre in der nächsten Zeile fertig gewesen. Nun sagt mein Lehrer aber, dass dies schon der Widerspruchsbeweis ist, nach dem Satz des Archimdeses (Also dieses, jede reelle Zahl wird von einer natürlichen übertroffen)

Ich komme jetzt allerdings nicht dahinter, warum ich dieses Argument bei

n+1 <= c anwenden kann und bei c>= 1 + (2/n) nicht?

Danke sehr