O-Notation / Landau-Symbole

[andi26]

Hallo zusammen,

ich habe ein wohl grundsätzliches Verständnisproblem bei der Abschätzung von oberen Schranken eines Algorithmus mit Hilfe der O-Notation. Hier ein Beispiel dazu, mit dem ich nicht klarkomme:

Gegeben sei folgender Sortieralgorithmus in JAVA:

public static void sort(int [] a) {

  int l, r, m, x;

  for (int i = 1; i < a.length; i++) {

    x = a[i];

    l = 0;

    r = i - 1;

    while (l <= r) {

      m = (l + r) / 2;

      if (x < a[m]) { r = m - 1; }

      else { l = m + 1; }

    }

    for (int j = i - 1; j >= l; j--) {

      a[j + 1] = a[j];

    }

    a[l] = x;

  }

}


[/PHP]

Die Frage lautet:

Wie viele Vergleiche - in Abhängigkeit von der Feldlänge von a - werden im obigen

Algorithmus getätigt? Geben Sie eine obere Schranke mit Hilfe der O-Notation an.

Begründen Sie ihr Ergebnis!

Wie gehe ich an so eine Frage ran? Kann mir da jemand weiterhelfen?

Ich würde mir jetzt als erstes die 1. For-Schleife anschauen, in der es m.E. zu a Vergleichen kommen müsste...

Vielen Dank für jeden Hinweis,

Andi

[MartinSt]

Hallo Andi

zu a Vergleichen kann es schonmal garnicht kommen, weil a ein Feld ist und die Anzahl der Sortiervorgänge wohl eine Zahl sein wird ;-)

Mit der O-Notation wird der Aufwand (des Sortierens) angegeben, in Abhängigkeit von der Anzahl der zu sortierenden Elemente im Feld.

Diese wird typischerweise mit n bezeichnet, so dass der Aufwand O eine Funktion von n ist.

O(n) wäre zB ein linear von n abhängiger Aufwand, O(n²) ein quadratisch wachsender Aufwand usw.

Du kannst nun in deinem Algorithmus die benötigten Vergleiche auszähken, in allen 3 Schleifen.

Gruß Martin

[andi26]

Hallo Martin,

vielen Dank für Deine schnelle Antwort!

zu a Vergleichen kann es schonmal garnicht kommen, weil a ein Feld ist und die Anzahl der Sortiervorgänge wohl eine Zahl sein wird ;-)

arg..da hast Du natürlich recht. Ich wollte eigentlich schreiben, dass es wohl a.length-1 Vergleiche gibt, was sich aber durch Deine Antwort jetzt eh erledigt hat

Du kannst nun in deinem Algorithmus die benötigten Vergleiche auszähken, in allen 3 Schleifen.

Ok, das heißt ich hätte für die erste for-Schleife n-1 Vergleiche. Und bei jedem dieser n-1 Vergleiche wird ja auch in der while Schleife ein Vergleich durchgeführt, weshalb ich dann wohl:

O(n) = (n-1) * [Anzahl Vergleiche in der while Schleife]

hätte, oder? Und wie komme ich auf die Vergleiche in der while-Schleife?

[Lizzy]

Ok, das heißt ich hätte für die erste for-Schleife n-1 Vergleiche.

Ja.

Und bei jedem dieser n-1 Vergleiche wird ja auch in der while Schleife ein Vergleich durchgeführt, weshalb ich dann wohl:

O(n) = (n-1) * [Anzahl Vergleiche in der while Schleife]

hätte, oder?

Die Gleichung ist Kaese. An der Stelle muss ich leider sagen, Du hast das O-Kalkuel noch in keiner Weise verstanden.

Und wie komme ich auf die Vergleiche in der while-Schleife?

Theoretisch gesehen: Rekursiv wieder das O-Kalkuel bzw. die O-Notation fuer die While-Schleife ermitteln.

Und was ist mit der anschliessenden For-Schleife?

Ich rezitiere nochmal die Aufgabenstellung, um Dir zu zeigen warum Du nochmal die Grundlagen des O-Kalkuels durcharbeiten solltest:

Wie viele Vergleiche - in Abhängigkeit von der Feldlänge von a - werden im obigen

Algorithmus getätigt?

Lasesst sich nicht vorraussagen. Wenn Du das schaffst, dann herzlichen Glueckwunsch! Dann ist Dir der Nobelpreis fuer Informatik/Mathematik sicher.

Geben Sie eine obere Schranke mit Hilfe der O-Notation an.

Bestaetigt mein vorheriges Statement. Wozu eine obere Schranke angeben, wenn man die Anzahl der Vergleiche punktgenau voraussagen koennte?

Begründen Sie ihr Ergebnis!

Auch ein Indiz dafuer, dass die Loesung ziemlich einfach ist, jedoch die Begruendung etwas schwieriger. Du darfst nicht versuchen nach einer Formel zu suchen, die Dir die Anzahl der Vergleiche liefert. Deshalb: Nochmal genau die Definition der O-Notation durchgehen, versuchen diese zu verstehen.

Kleiner Tip: Es gibt 2 Begruendungspunkte, die angefuehrt werden sollten.

Gruesse,

Lizzy

[MartinSt]

Ja.

Wenn Du das schaffst, dann herzlichen Glueckwunsch! Dann ist Dir der Nobelpreis fuer Informatik/Mathematik sicher.

<humor>

Der Preis müßte aber erst noch erfunden werden, vielleicht würde es ja zur Not auch die Fields-Medaille tun. </humor>

Aber nochmal zur O-Notation und zum eigentlichen Thema ...

die gesuchte Schranke gibt dir immer nur eine Obergrenze des Aufwandes selbst im schlechtmöglichsten Fall an.

Falls die Aufgabe aus dem Informatikstudium herrührt, dann erinnere dich mal an den Analysis-Kurs und die dort beliebten oberen/unteren Schranken für Funktionen.

Gruß Martin

[setiII]

Und bei jedem dieser n-1 Vergleiche wird ja auch in der while Schleife ein Vergleich durchgeführt, weshalb ich dann wohl:

O(n) = (n-1) * [Anzahl Vergleiche in der while Schleife]

hätte, oder?

Wenn du "[Anzahl Vergleiche in der while Schleife]" annähernd "n" annimmst, wirds wohl eher ein O(n^2).

Und das annähernd meine ich bei einer betrachtung gegen unendlich

[andi26]

Hallo zusammen,

vielen Dank für euere zahlreichen Antworten. Ja, Lizzy, da hast Du recht, ich hab wohl wirklich noch nichts verstanden. Deshalb bin ich ja auch hier Zunächst würd ich mich auch damit begnügen meine Prüfung zu schaffen und die Sache mit dem Nobellpreis auf später zu verschieben

Ich hab mir die Sache jetzt noch mal ein bisschen angeschaut, aber mit der formellen Definition der Oberen Schranke

O(f ) = g : N → R+ | ∃c > 0 ∃n0 > 0 ∀n ≥ n0 : g(n) ≤ c ∗ f (n)

Komme ich nicht wirklich gut klar.

Was ich in den Unterlagen noch gefunden habe, sind "typische Laufzeitverhalten" für typische Anweisungen (for Schleifen, while Schleifen, ...). Dort ist angegeben:

for Schleife: O(n)

while Schleife: O(log2 n)

In meinem Programm habe ich ja im Grunde die Struktur:

for (..){

while(...)

}

for (...){

}

Da mich nur der größere Kandidat interessiert, ist hier wohl nur die 1. for-Schleife (mit seinem while) interessant. Sprich, der Algorithmus könnte insgesamt die obere Schranke O(n) oder O(log2 n) haben. Bin ich schon näher dran?

Viele Grüße, Andi

[MartinSt]

Hi Andy

überlege dir doch einfach mal, wie oft (in Abhängigkeit von der äußeren for-Schleife) die while-Schleife durchlaufen wird. Wenn du dann den Aufwand für die while-Schleife nimmst hast, hast du sowhol sprachlich als auch mathematisch die Lösung. ;-)

Gruß Martin

[andi26]

überlege dir doch einfach mal, wie oft (in Abhängigkeit von der äußeren for-Schleife) die while-Schleife durchlaufen wird. Wenn du dann den Aufwand für die while-Schleife nimmst hast, hast du sowhol sprachlich als auch mathematisch die Lösung. ;-)

Kann man das so allgemein sagen wie oft die while-Schleife in Abhängigkeit von der for-Schleife ausgeführt wird? Ich konnte da keine allgemeine Beziehung herstellen...

Aber wenn Du schreibst dass der Aufwand der while-Schleife der Aufwand des gesamten Algorithmus ist, dann ist die Lösung wohl O(log2 n). Ich versteh aber noch nicht so ganz warum das so ist? Und begründen müsste ich das ja in der Aufgabe leider auch noch...

[MartinSt]

Kann man das so allgemein sagen wie oft die while-Schleife in Abhängigkeit von der for-Schleife ausgeführt wird?

ja

Aber wenn Du schreibst dass der Aufwand der while-Schleife der Aufwand des gesamten Algorithmus ist, dann ist die Lösung wohl O(log2 n).

Das habe ich nicht geschrieben

Stell dir doch mal vor, dass Du diesen Code im Debugger laufen läßt und auf der while-Anweisung einen Breakpoint hast.

Wieoft wird dann an diesem Breakpoint gestoppt ?

Gruß Martin

[andi26]

ja

Stell dir doch mal vor, dass Du diesen Code im Debugger laufen läßt und auf der while-Anweisung einen Breakpoint hast.

Wieoft wird dann an diesem Breakpoint gestoppt ?

Gruß Martin

Hmm...da ich mein Feld in der Mitte teile (m) und l und r dann zwischen 0 und m immer weiter aufeinander zumarschieren würde ich sagen die while Schleife wird immer halb so oft i/2 mal ausgeführt...

EDIT: n/2 mal meinte ich...

[MartinSt]

Hallo

das Halbieren wird doch innerhalb der while-Schleife gemacht, aber was innerhalb dieser Schleife passiert, ist erstmal egal. Wichtig ist, wie oft sie ausgeführt wird oder anders gefragt, wie oft würde ein Breakpoint, der auf dem while sitzt, angesprungen.

Gruß Martin

[andi26]

Hmm...der Grund warum ich mich um das Innere der while-Schleife gekümmert hab, war, weil sie ja geht so lange l kleiner gleich r und l und r ja innerhalb der while-Schleife verändert werden.

Aber wenn ich den Inhalt mal ignoriere und nur von der for Schleife ausgehe:

l wird auf 0 gesetzt,

r wird auf i-1 gesetzt

Da i von 1 bis Feldlänge (also n) geht und l da immer kleiner gleich r ist, würde ich sagen die while-Schleife wird n mal ausgeführt...

[Lizzy]

Ich hab mir die Sache jetzt noch mal ein bisschen angeschaut, aber mit der formellen Definition der Oberen Schranke

O(f ) = g : N → R+ | ∃c > 0 ∃n0 > 0 ∀n ≥ n0 : g(n) ≤ c ∗ f (n)

Komme ich nicht wirklich gut klar.

Sinnvoll, um so etwas zu verstehen, ist sich dies einfach mal in Einzelteilen als Text zu formulieren.

O(f ) = [color=red]g : N → R+[/color] | ∃c > 0 ∃n0 > 0 ∀n ≥ n0 : g(n) ≤ c ∗ f (n)

1. g ist eine Funktion, die eine natuerliche Zahl auf eine positive reelle Zahl abbildet. (In diesem Fall formuliert g die Laufzeit [R+] eines Algorithmus in Abhaengigkeit der Eingabemenge [N].)

O(f ) = g : N → R+ | ∃c > 0 ∃n0 > 0 ∀n ≥ n0 : [color=red]g(n) ≤ c ∗ f (n)[/color]

2. Es existiert eine Funktion f, deren Ergebnis stets groesser oder gleich dem Ergebnis von g ist, wenn man sie mit dem gleichen n "fuettert" und sie mit einer Konstanten c multipliziert.

O(f ) = g : N → R+ | [color=red]∃c > 0[/color] ∃n0 > 0 ∀n ≥ n0 : g(n) ≤ c ∗ f (n)

3. Voraussetzung 1 ist dabei, dass der Faktor c eine Zahl groesser 0 ist.

O(f ) = g : N → R+ | ∃c > 0[/color] [color=red]∃n0 > 0 ∀n ≥ n0

: g(n) ≤ c ∗ f (n) 4. Es gibt eine untere Schranke n0, die positiv ist und ab der fuer alle groesseren Werte fuer n die obigen Bedingungen gelten. Also nochmal zusammengefasst: 1. g ist eine Funktion, die eine natuerliche Zahl auf eine positive reelle Zahl abbildet. (In diesem Fall formuliert g die Laufzeit [R+] eines Algorithmus in Abhaengigkeit der Eingabemenge [N].) 2. Es existiert eine Funktion f, deren Ergebnis stets groesser oder gleich dem Ergebnis von g ist, wenn man sie mit dem gleichen n "fuettert" und sie mit einer Konstanten c multipliziert. 3. Voraussetzung 1 ist dabei, dass der Faktor c eine Zahl groesser 0 ist. 4. Es gibt eine untere Schranke n0, die positiv ist und ab der fuer alle groesseren Werte fuer n die obigen Bedingungen gelten. Punkt 1 ist eigentlich das, was wir haben und was quasi durch den Algorithmus feststeht. Nehmen wir an bei n Eingabedaten benoetigt ein Algorithmus durch 2 For-Schleifen (jeweils von 1 bis n) bedingt insgesamt 2 * n Zeiteinheiten und zusaetzlich 5 Zeiteinheiten einmaliger Overhead, der unabhaengig von n ist. Dann waere unsere Funktion g:

g(n) = 2 * n + 5

Was wir suchen ist eine Funktion f, die bei gleichem n einen groesseren oder gleichen Wert wie g liefert, wenn wir sie mit einer Konstanten c multiplizieren (Punkt 2). Ziel des O-Kalkuels ist es, eine moeglichst einfache Funktion zu finden, z.B.

f(n) = 7 * n

Daraus kann man eigentlich schonmal ableiten, dass Konstante Werte, die unabhaengig von n sind, im O-Kalkuel immer rausfliegen. Man braucht den Faktor c nur genuegend gross waehlen. Da in Punkt 2 aber schon gesagt wird, dass f(n) mit einem beliebigen positiven c multipliziert wird, koennen wir auch den Konstanten Faktor 7 weglassen und erhalten

f(n) = n

Somit erhalten wir als Aufwand des Algorithmus O(n). Punkt 4 sagt uns nebenbei noch, dass g(n) <= f(n) erst ab einem bestimmten Wert n0 gelten muss. Der konstante Faktor c braeuchte noch nicht einmal 7 sein, sondern 3 wuerde vollkommen ausreichen. n0 waere dann 5. Ab einem Wert von 5 waeren die Bedingung erfuellt. Aber das nur nebenbei. Hoffe, das war einigermassen lesbar und traegt ein wenig zum Verstaendnis des O-Kalkuels bei bzw. der genannten Formel bei.

Was ich in den Unterlagen noch gefunden habe, sind "typische Laufzeitverhalten" für typische Anweisungen (for Schleifen, while Schleifen, ...). Dort ist angegeben: for Schleife: O(n) while Schleife: O(log2 n)

Bei solchen Vereinfachungen sollten man IMMER sehr, sehr vorsichtig sein. Jede For-Schleife kann ich auch vollkommen aequivalent als While-Schleife darstellen - dabei aendert sich nichts am O-Kalkuel. Ebenso gilt das O(n) auch nur fuer For-Schleifen im klassischen Sinn. Ganz gemeines (wenn auch sehr kuenstlich konstruiertes) Beispiel:

  for (int i = 0; i < Round(Log(n)); i++)

  {

      ...

  } 

Zwar eine For-Schleife, ist aber trotzdem O(log n). ;-)

Bestimmte Konstrukte koennen durchaus Anhaltspunkte fuer den Aufwand sein, aber sicherlich keine stets zuverlaessigen.

------------------

Sooo... und nach diesem "kleinen" Exkurs nochmal zum eigentlichen Problem, also zum Algorithmus aus der Aufgabenstellung.

Dass die aeussere For-Schleife n-mal durchlaufen wird steht denke ich ausser Frage. Bleibt also noch eine innere While-Schleife und eine innere For-Schleife.

Preisfrage: Laesst sich bei diesen beiden Schleifen der Aufwand eindeutig bestimmen?

Antwort: Nein. Die Anzahl der Durchlaeufe beider Schleifen haengt nicht nur von der Anzahl der Elemente im Array a ab, sondern auch von den Werten, die im Array enthalten sind.

Da kann man jetzt zwischen worst case, average case und best case unterscheiden. Da nach einer oberen Schranke gefragt wird, wuerde ich persoenlich den worst case annehmen.

Also die Frage: Wie oft werden die inneren Schleifen im unguenstigsten Fall durchlaufen.

Genau das sollte in der Begruendung fuer die gefundene O-Notation dann auch explizit auftauchen. Warum betrachte ich den worst-case? Und wie komme ich dann auf die genannte O-Notation.

Gruesse,

Lizzy

[andi26]

Liebe Lizzy,

leider habe ich gerade keine Zeit, Deine Antwort durchzudenken - ich melde mich morgen oder übermorgen - nur damit Du nicht meinst, Dein ausführlicher Beitrag bleibt unbeantwortet :-)

[Lizzy]

Liebe Lizzy,

*huestel*, bitte lieber Lizzy oder einfach "Hey Lizzy!" ;-)

Mein Internet-Nick ist im Laufe der Jahre zu Lizzy mutiert, ruehrt aber nicht von Elisabeth oder aehnlichem her. Ich nehme eine Verwechslung aber nicht krumm. Das suesseste, was ich mal aus Suedamerika geschrieben bekommen habe: "You rock, sister!" ;-)

leider habe ich gerade keine Zeit, Deine Antwort durchzudenken - ich melde mich morgen oder übermorgen - nur damit Du nicht meinst, Dein ausführlicher Beitrag bleibt unbeantwortet :-)

Ist schon in Ordnung. War fuer mich selbst auch ein Weg mal altes Wissen aufzufrischen und in Worte zu packen. Von daher bin ich da auf Antworten auch nicht ungeduldig.

Gruesse,

der Lizzy^^

[andi26]

Liebe Lizzy,

so, jetzt hab ich endlich Zeit :-)

Vielen Dank für Deine ausführliche Beschreibung der O-Notation - ich glaube jetzt ist mir das klarer.

Zum Algorithmus: Ok, dass man den worst-case nehmen muss leuchtet mir ein. Mittlerweile ist mir auch in der Vorlesung die Lösung präsentiert worden, die da heißt:

n * ld n

Das erste n (für die äußere Schleife) ist mir klar. Dass die zweite For-Schleife weggelassen wird (vernachlässigbar, weil Aufwand für die erste For-Schleife größer) ist mir auch klar. Aber warum wird die while-Schleife im schlechtesten Fall ld n mal durchlaufen (ld = log zur Basis 2)?

[Klotzkopp]

Aber warum wird die while-Schleife im schlechtesten Fall ld n mal durchlaufen (ld = log zur Basis 2)?

Schau dir doch mal genau aus, was in dieser Schleife passiert. In der Schleife werden l und r aufeinander zu bewegt. Die Art und Weise, wie das passiert (und wie sich der Abstand der beiden dabei entwickelt), ist der springende Punkt.

[Lizzy]

Dass die zweite For-Schleife weggelassen wird (vernachlässigbar, weil Aufwand für die erste For-Schleife größer) ist mir auch klar. ?

Das ist eigentlich nicht der Punkt. Es wird nichts weggelassen, weil der Aufwand fuer eine aeussere Schleife groesser ist. Nehmen wir mal an, die aeussere Schleife haette einen Aufwand von n^2 und eine innere Schleife von n. Dann wuerde man auch nicht sagen insgesamt ist der Aufwand O(n^2), da der Aufwand der inneren Schleife vernachlaessigbar ist.

Wenn ich das gerade nicht falsch ueberblicke duerfte der gesamte Aufwand innerhalb der aeusseren For-Schleife 2*ld(n) sein. Die 2 ist dabei wieder unsere geliebte Konstante c, die durch die Definition des O-Kalkuels unter den Tisch faellt. Daher dann insgesamt O(n*ld(n)).

Die Anzahl in der inneren For-Schleife haengt stark von der vorangehenden While-Schleife ab. Deshalb kommt hier auch wieder der Logarithmus in's Spiel, und das haengt, wie Klotzkopp richtig geschrieben hat, von der Art und Weise ab, wie sich l und r aufeinander zubewegen

Gruesse,

DER Lizzy ;-)

[MartinSt]

*huestel*, bitte lieber Lizzy oder einfach "Hey Lizzy!" ;-)

darf ich auch Thin Lizzy sagen ?