Big O notation?

Wie löst man die obige Aufgabe. Habe mir jetzt ein paar Videos zum Thema angeschaut und kann ein paar Algorithmen analysieren. Bei obigem komme ich aber nicht weiter.

Beim ersten Algorithmus muss ich die Multiplikation ja jedes mal durchführen, während beim zweiten nur ein einziges mal am Ende multipliziert wird. Daher hätte ich gesagt:

1. Algorithmus O(n), da ich die Multiplikation jedes mal durchführen muss
2. Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Meine Fragen:

1. Ist die Analyse korrekt?
2. Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?
3. Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

Answer 1

[Quotenbanane]

Das Ergebnis sollte in dem Fall in der Big O Notation dasselbe sein. Es kommt darauf an, was x_i genau ist, aber hätte man k = max_{i in IN} (x_i) < unendlich, kann man sagen, dass der Ausdruck in O(n*k) = O(n) ist.

Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Das kann es schon mal rein logisch nicht sein, weil du trotzdem n Summen hast.

Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?

In dem Fall ohne Kenntnis von x_i schwer. Falls x_i bekannt, kann man abschätzen oder im Fall einer arithmetischen/geometrischen Reihe deren Summenformeln anwenden.

Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

Was genau versteht die Aufgabe (oder du) unter T bzw. O?

Comments

[Halbrecht]

Schon seltsam : FS stellt noch mal ein , antwortet aber nicht auf deinen Nachfrage

Answer 2

[magicced01]

1)Es ist beides O(n) und Theta(n) das erste ist trivial wir haben einfach n viele Additionsschritte. beim zweiten mal haben wir eine Konstante also O(1) mal n viele Additionsschritte

2) Man kann das über den Limes oder über Existenzquantoren beweisen schau dir halt mal die Landau Notation wiki page an Landau-Symbole – Wikipedia

3) Einfach gesagt O ist die obere Schranke und Theta die genaue schranke. Zum Beispiel ist n in O(n^2) aber in Theta(n)