O Notation von zwei verschachtelten Schleifen

seux

Hallo,
wie kann ich die O-Notation der folgenden Pseudo Schleifenkonstruktion bestimmen.

for(int i = 0; i < grenze; i++) {
     ...
     for(int j = i + 1; j < grenze; j++) {
          ...
     }
}

Die äußere Schleife wäre doch O(grenze), also O(n). Aber wie macht man das mit der inneren schleife. Immerhin hängt sie von der äußeren Schleife ab.

gruß
seux

Michael E.

\begin{align*}\mathcal{O}\left(\sum_{i=0}^{x - 1} \sum_{j=i+1}^{x - 1} 1\right) = \mathcal{O}\left(\sum_{i=0}^{x - 1} (x - i)\right) = \mathcal{O}\left(\sum_{i=0}^{x - 1} i\right) = \mathcal{O}(x^2)\end{align*}.

Edit: Latex-Typo.

seux

Danke für deine Hilfe, aber so ganz Blick ich da durch deine umformung noch nicht durch. Wie du auf den ersten Teil mit den Zwei summen kommst, versteh ich.

$\sum_{j=i+1}^{x - 1} 1$
müsste das nicht zu (x-2 - i) werden?

Und wie kommst du von (x - i) auf i?

Und im letzten Schritt:
Das i wird doch x-1 mal aufsummiert, also i+i+i+i+i+...
also (x-1)*i. Wie kommst du da auch x²

hustbaer

seux schrieb:

Und wie kommst du von (x - i) auf i?

muss auch x heissen statt i

seux schrieb:

Und im letzten Schritt:
Das i wird doch x-1 mal aufsummiert, also i+i+i+i+i+...
also (x-1)*i. Wie kommst du da auch x²

1 + 2 + 3 + ... + x = x(x+1)/2 = O(x²)

Michael E.

seux schrieb:

$\sum_{j=i+1}^{x - 1} 1$
müsste das nicht zu (x-2 - i) werden?

Die 2 verschwindet in der O-Notation.

hustbaer schrieb:

seux schrieb:

Und wie kommst du von (x - i) auf i?

muss auch x heissen statt i

Ne, das passt schon. Ist eine einfache Indextransformation $i := x - i$ . Weil ich mir auch hier keine Gedanken um Offset-Fehler machen wollte, steht das Ganze in O-Notation.

Edit: Wobei x statt i als obere Abschätzung natürlich auch nicht verkehrt wäre und zum selben Ergebnis führt.

hustbaer

@Michael E.
Uff, wenn du das sagst
Das Ergebnis ist mit nur i das selbe, das stimmt.
Warum man das einfach so machen darf ist mir nicht klar - ist aber auch nicht wichtig.

EDIT: Ahhh... verstehe. Indextransformation. OK. Ich hatte angenommen dass das was mit der O Notation zu tun haben müsste, und hab daher den Wald vor lauter Bäumen nicht gesehen.

seux

Vielen Dank für die hilfreichen Antworten, hat geholfen

hustbaer

Er...
Jetzt doch nochmal ne Frage...

\begin{align*}\sum_{i=0}^{x - 1} (x - i)\end{align*}
Wenn wir da jetzt ne Indextransformation $i := x - i$ machen, müsste dann nicht \begin{align*}\sum_{i=1}^{x} i\end{align*} rauskommen?

Michael E.

Das stimmt, geht aber wiederum in der O-Notation verloren. Nächstes Mal mache ich die Rechnung einfach exakt, wenn ich sehe, was ich hier an Verwirrung gestiftet habe

Zeiger44

Hallo,

ich möchte bei einer ähnlichen Konstruktion die Laufzeit abschätzen, nur dort sind noch zwei Substrings drin. Wie wird damit verfahren?

for(int i = 0; i < strlen(str1)-2; i++) {

     for(int j =0; j < strlen(str2)-2; j++) 
     {
         substr(str1,i,2);
         substr(str2,j,2);
     }
}

Michael E.

Durch die substr ändert sich nix, da sie beide nur konstanten Aufwand haben. Eine wichtigere Änderung ist, dass die beiden Schleifenvariablen bei dir nicht voneinander abhängen. Bei dir kommt daher O(strlen(str1) * strlen(str2)) raus.

Michael E. schrieb:

Bei dir kommt daher O(strlen(str1) * strlen(str2)) raus.

Gibts sowas? Ist das nicht O(n²), wenn strlen konstanten Aufwand hat.

grüßGott schrieb:

Michael E. schrieb:

Bei dir kommt daher O(strlen(str1) * strlen(str2)) raus.

Gibts sowas? Ist das nicht O(n²), wenn strlen konstanten Aufwand hat.

was ist denn $n$ ?