PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Laufzeitverhalten von Algorithmen (einfaches Niveau)


irinaM
2010-07-16, 20:51:12
Hallo!

Bin gerade an einer kleinen Aufgabe, bei welcher die Größenordnung der Zeitkomplexität bestimmt werden soll. Dabei geht es allerdings lediglich um Schleifenkonstrukte, deren Rumpf keine Rolle spielt, es sei denn er manipuliert die Zählvariablen der Schleifen.

Beispiel: eine Schleife hat n als Komplexität, 2 Schleifen hintereinander 2n, 2 verschachtelte Schleifen n^2 usw.

Hier gleich eine einfache Frage: wären 2 verschachtelte Schleifen, bei der die innere pro Durchlauf der äußeren einen Durchlauf weniger macht, n*log n?

n, da die äußere immer komplett durchläuft, die innere aber reduziert wird - wäre jetzt meine Vermutung gewesen.

Dann noch 2 konkrete Beispiele, eventuell könnt ihr sagen ob meine Gedanken richtig sind:


int func(int n) {
int k = 1;
while (k < n) k = k * 2;
for(int i = 1; i < n * n; i++) {
for(int j = 1; j < 10; j++) k++;
}
return k/2;
}


Erstmal zur Verschachtelung, man könnte schnell auf n^2 kommen, da die Laufvariablen isoliert sind - das n*n der äußeren Schleife macht das ganze dann aber doch zum n^3?

Die while-Schleife irritiert mich etwas... eventuell log n, da bei größeren n die Bedingung viel schneller erfüllt wird? Bei n = 16 wäre man für k mit den Schritten 2-4-8-16 und somit 4 Durchläufen am Ziel, für n =32 braucht man allerdings nur einen Durchlauf mehr.
Im großen und ganzen dürfte das gegen die verschachtelten Schleifen unten aber sowieso nicht ins Gewicht fallen.


Noch ein letzter:


int func(int n) {
int k = 1;
for (int p= n; p > 1; p = p/2) {
while (k < n+n) k = k + 2;
}
return k;
}


Die äußere Schleife eventuell wieder log n, da bei größeren n die Laufzeit nicht mehr so stark zunimmt, Beispiel:

p=1000 /2 = 500 /2 = 250 /2 = 125 /2 = 62 /2 = 31 /2 = 15 /2 = 7 /2 = 3 /2 = 1
Also 9 Läufe

p=16000 /2 = 8000 /2 =4000 /2 = 2000 /2 = 1000 /2 = 500 /2 = 250 /2 = 125 /2 = 62 /2 = 31 /2 = 15 /2 = 7 /2 = 3 /2 = 1
Also 13 Läufe, gerade mal das 1,4 fache mehr für ein p, welches 16 mal so groß is?

Die innere Schleife sieht linear, also nach n aus.

Gesamt also n * log n?


Würde mich über Antworten freuen, vielen Dank! :)

Magnum
2010-07-16, 21:35:55
Hier gleich eine einfache Frage: wären 2 verschachtelte Schleifen, bei der die innere pro Durchlauf der äußeren einen Durchlauf weniger macht, n*log n?

n, da die äußere immer komplett durchläuft, die innere aber reduziert wird - wäre jetzt meine Vermutung gewesen.
Hier liegst du falsch. Die Komplexität bleibt bei O(n²). Genauer glaube ich bei nur n*(n-1), müsste ich aber nochmal nachschauen. Ist nur ausm Gedächtnis. (Edit: könnten auch n²/2 sein)


int func(int n) {
int k = 1;
while (k < n) k = k * 2;
for(int i = 1; i < n * n; i++) {
for(int j = 1; j < 10; j++) k++;
}
return k/2;
}


Erstmal zur Verschachtelung, man könnte schnell auf n^2 kommen, da die Laufvariablen isoliert sind - das n*n der äußeren Schleife macht das ganze dann aber doch zum n^3?

Die while-Schleife irritiert mich etwas... eventuell log n, da bei größeren n die Bedingung viel schneller erfüllt wird? Bei n = 16 wäre man für k mit den Schritten 2-4-8-16 und somit 4 Durchläufen am Ziel, für n =32 braucht man allerdings nur einen Durchlauf mehr.
Im großen und ganzen dürfte das gegen die verschachtelten Schleifen unten aber sowieso nicht ins Gewicht fallen.
Die while-Schleife fällt hier nicht ins Gewicht. Deren Laufzeit liegt bei log n. Die äußere Schleife liegt wie schon gesagt bei O(n²), die innere hat eine konstante Laufzeit. Zusammen liegen sie also in O(n²+log n) = O(n²).


int func(int n) {
int k = 1;
for (int p= n; p > 1; p = p/2) {
while (k < n+n) k = k + 2;
}
return k;
}


Die äußere Schleife eventuell wieder log n, da bei größeren n die Laufzeit nicht mehr so stark zunimmt, Beispiel:

p=1000 /2 = 500 /2 = 250 /2 = 125 /2 = 62 /2 = 31 /2 = 15 /2 = 7 /2 = 3 /2 = 1
Also 9 Läufe

p=16000 /2 = 8000 /2 =4000 /2 = 2000 /2 = 1000 /2 = 500 /2 = 250 /2 = 125 /2 = 62 /2 = 31 /2 = 15 /2 = 7 /2 = 3 /2 = 1
Also 13 Läufe, gerade mal das 1,4 fache mehr für ein p, welches 16 mal so groß is?

Die innere Schleife sieht linear, also nach n aus.

Gesamt also n * log n?
Die for Schleife ist, wie erkannt, logarithmisch. Also O(log n). Die Innere Schleife ist auch tatsächlich linear. Soweit so gut.
Allerdings wird die Bedingung der inneren Schleifen von der äußere nicht beeinflusst, ist also nur im ersten Durchlauf linear, in allen anderen wird sie nicht ausgeführt (Bedingung schon erfüllt). Macht also in der Summe: O(1*n + (log n)*1) = O(n).

Ich hoffe das hilft dir weiter. Alle Angaben ohne Gewähr. Darf alo gern korrigiert werden!

Neomi
2010-07-16, 22:39:54
Die konkreten Laufzeitverhalten hat Magnum ja schon genannt (hab da keinen Fehler gefunden), aber allgemein solltest du (Threadstarter) anders an die Sachen herangehen.

Du schaust bei Schleifen einfach darauf, ob ihre Iteratoren linear oder anders durchlaufen, aber das ist völlig irrelevant. Die Schleife von 1 bis 10 in deinem einen Beispiel läuft genau 10x durch, völlig egal wie groß n ist. Wie soll die da einen Einfluß auf das Laufzeitverhalten in Abhängigkeit von n haben können? Einzig und alleine relevant sind Schleifen, die in Abhängigkeit von n unterschiedlich oft durchlaufen. Wenn du dir bei einem Algorithmus nicht sicher bist, dann nimm einen Zähler (oder mehrere) dazu, den du innerhalb der Schleifen an passend aussehenden Stellen erhöhst. Dann kannst du mit verschiedenen n ganz einfach zählen lassen, wie das Laufzeitverhalten aussieht.

irinaM
2010-07-16, 22:56:21
Vielen Dank schonmal, mir ist einiges klarer geworden! :)

Die äußere Schleife liegt wie schon gesagt bei O(n²), die innere hat eine konstante Laufzeit. Zusammen liegen sie also in O(n²+log n) = O(n²).

Mein Fehler, habe im Eifer des Gefechts die konstante 10 übersehen. Warum ist es aber n²+log n statt multipliziert ? Auch wenn die innere Konstant ist, verschachtelt ist es doch trotzdem noch und wird pro äußerer Durchlauf einmal ausgeführt. Also im wörtlichen Sinne "ich mache n² mal irgendwas.."

Allerdings wird die Bedingung der inneren Schleifen von der äußere nicht beeinflusst, ist also nur im ersten Durchlauf linear, in allen anderen wird sie nicht ausgeführt (Bedingung schon erfüllt). Macht also in der Summe: O(1*n + (log n)*1) = O(n).

Ah, das hätte ich sehen müssen, stimmt. In diesem Fall ist mir auch klar, warum es trotz Verschachtelung eine Addition ist, wird ja nur einmal ausgeführt. Vielleicht könntest du mir noch erklären, wie man von n+log n auf n kommt. Eigentlich ist ja die äußere Schleife mit log n stark maßgebend, während die innere Schleife ja sogar nur einmal durchlaufen wird.


Neomi: vielen Dank für deinen Tipp, klingt nach einer guten Strategie. In meinem Fall hab ich das mit der 10 aber einfach übersehen.

Danke!

irinaM
2010-07-16, 23:03:18
Ich nochmal, Arg, das "log n +" kommt ja von der while-Schleife, sorry. Die 2. Frage bleibt aber noch :)

Gast
2010-07-17, 00:34:54
Das O(n+log(n))=O(n) ergibt sich aus der Definition der O Notation.

Als Beispiel eine Abschätzung: n+log(n) <= n+n = 2n

Damit haben wir eine beschränkende Funktion gefunden und wir können z.B. wählen: c=2, n0=1, mit denen dann gilt mit g(n) = n+log(n) und f(n)=n:

g(n) <=c*f(n)

Damit gilt: n+log(n) = O(n)

Neomi
2010-07-17, 01:30:42
Eigentlich ist ja die äußere Schleife mit log n stark maßgebend, während die innere Schleife ja sogar nur einmal durchlaufen wird.

Die innere Schleife mit O(n) wird zwar nur einmal durchlaufen, die äußere mit O(log n) aber natürlich auch nur einmal. Wenn du die innere Schleife eine Ebene nach draußen ziehst (und das geht, da sie ja nur einmal durchlaufen wird), wird es offensichtlicher, denn dann hast du zwei unabhängige Schleifen nebeneinander.

irinaM
2010-07-17, 16:21:41
So langsam macht es Klick, danke nochmal :)

Zum Abschluss noch ein paar theoretische Aussagen, die bewertet werden sollen. Die meisten waren sehr eindeutig, bei folgenden frag ich nochmal nach (grob aus dem Kopf, bin grad nicht daheim)

1. Ein Array zu sotieren ist immer n^2

Da Bubblesort mit n^2 als sehr schlechtes Verfahren gilt würde ich mal sagen es geht noch besser, also wäre die Antwort 'falsch'. Allerdings ist das trickreich, Shakersort ist ja auch viel effizienter als Bubblesort und hat trotzdem n^2.

2. Listen sind schneller zu durchsuchen als Arrays

Denke mal das ist falsch, für Dinge wie Binärsuche braucht man ja einen Index.

3. Quicksort ist endrekursiv, weil es sich AM ENDE der Methode selbst aufruft und danach nichts mehr steht.

Stimmt zwar, aber der Aufruf steht dort ja 2 mal in Folge, imho nicht endrekusriv?

4. Bei Insertionsort gibt es bei einer Eingabemenge von n immer n-1 Suchvorgänge... müsste passen?


Danke nochmals an alle

PatkIllA
2010-07-17, 16:34:28
Bei allgemeinen Sortierverfahren ist O(n log(n)) der bester Worst Case den ein Verfahren bieten kann.

Pinoccio
2010-07-17, 17:15:20
Bei allgemeinen Sortierverfahren ist O(n log(n)) der bester Worst Case den ein Verfahren bieten kann.Klarstellung/Ergänzung: Allgemein heißt Vergleichsbasiert und ohne Parrallelisierung.
2. Listen sind schneller zu durchsuchen als Arrays

Denke mal das ist falsch, für Dinge wie Binärsuche braucht man ja einen Index.Dort (http://www.forum-3dcenter.org/vbulletin/showthread.php?t=482121) ist schon mal über sowas diskutiert worden.
Je nach dem, wie streng/abgrenzend/einschließend Liste definiert ist, ist die Antwort auf diese Frage.

mfg