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)?

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 :-)

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...

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...

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...

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 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

Hallo Martin, vielen Dank für Deine schnelle Antwort! 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 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?

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