Laufzeit

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo Leute, habe folgende frage zu dieser Aufgabe:

Gegeben seien die folgenden Laufzeitverhalten log n, n2, 2n, n log n, n! von fünf verschiedenen Algorithmen, die das gleiche Problem lösen. Diskutieren Sie die Laufzeitverhalten und filtern Sie jeweils den effizientesten Algorithmus für kleine, mittlere und große n (element) N heraus.

Nehmen wir an, dass zwei Algorithmen dasselbe Laufzeitverhalten (z.B. O(n log n)) haben. Erläutern Sie warum dies nicht bedeutet, dass beide auch die gleiche Laufzeit haben.

log n ist doch das effizienteste Algorithmus für kleine, mittlere und große n´s ? (egal was für eine Zahl ich einsätzte mit log n habe ich das kleinste ergebnis) oder habe ich da was falsch verstanden?

zum zweiten teil: was ist der unterschied zw. laufzeitverhalten und laufzeit? warum müssen die nicht gleich sein?

vielen dank

#2

zum zweiten teil: was ist der unterschied zw.
laufzeitverhalten und laufzeit? warum müssen die nicht gleich
sein?

Das ergibt sich direkt aus der Definiton der O-Notation. (Tipp: überleg mal, wie sich z.B. O(1) zu O(n) verhält.)

#3

Hallo Leute, habe folgende frage zu dieser Aufgabe:

Gegeben seien die folgenden Laufzeitverhalten log n, n2, 2n, n
log n, n! von fünf verschiedenen Algorithmen, die das gleiche
Problem lösen. Diskutieren Sie die Laufzeitverhalten und
filtern Sie jeweils den effizientesten Algorithmus für kleine,
mittlere und große n (element) N heraus.

Nehmen wir an, dass zwei Algorithmen dasselbe
Laufzeitverhalten (z.B. O(n log n)) haben. Erläutern Sie warum
dies nicht bedeutet, dass beide auch die gleiche Laufzeit
haben.

log n ist doch das effizienteste Algorithmus für kleine,
mittlere und große n´s ? (egal was für eine Zahl ich einsätzte
mit log n habe ich das kleinste ergebnis) oder habe ich da was
falsch verstanden?

Würde ich auch sagen.

zum zweiten teil: was ist der unterschied zw.
laufzeitverhalten und laufzeit? warum müssen die nicht gleich
sein?

Mit O(x) beschreibt man ja nur, wie sich die Ausführungszeit eines konkreten (und konstanten) Algorithmus abhängig von der Anzahl der zu bearbeitenden Fälle/Elemente verändert.
Dabei kann es aber gut sein, dass 2 unterschiedliche Algorithmen unterschiedlich lange für ihr Ergebnis brauchen.
Beispiel: Algo1 braucht für 10 Elemente 10 sek, für 20 Elemente 20 sek usw, hat also O(n).
Algo2 braucht für 10 Elemente nur 5 sek, für 20 Elemente 10 sek usw, hat also auch O(n), aber eine halb so große Laufzeit.

vielen dank

Gerne,
Martin

#4

Hallo Fragewurm,

zum zweiten teil: was ist der unterschied zw.
laufzeitverhalten und laufzeit? warum müssen die nicht gleich
sein?

Wobei noch hinzuzufügen ist, dass das Laufzeizverhalten in der Praxis NOCH komplizierter ist als es schon beschrieben wurde.

Ein Algorithmus O(n) wird in der Praxis keine lineare Abhängigkeit der Laufzeit aufweisen, besonders bei kleinen n und kleinen Datenmengen pro Element.

  1. Die Ladezeit und die Zeiten für das Öffnen/Schliessen von Dateien ist unabhängig von n.
  2. Die diversen Zwischenspeicher (Cache) und die Speicherverwaltung verursachen einen nicht linearen Anstieg der der Laufzeit in abhängigkeit von n.

MfG Peter(TOO)

#5

Mit O(x) beschreibt man ja nur, wie sich die Ausführungszeit
eines konkreten (und konstanten) Algorithmus abhängig von der
Anzahl der zu bearbeitenden Fälle/Elemente verändert.
Dabei kann es aber gut sein, dass 2 unterschiedliche
Algorithmen unterschiedlich lange für ihr Ergebnis brauchen.
Beispiel: Algo1 braucht für 10 Elemente 10 sek, für 20
Elemente 20 sek usw, hat also O(n).
Algo2 braucht für 10 Elemente nur 5 sek, für 20 Elemente 10
sek usw, hat also auch O(n), aber eine halb so große Laufzeit.

danke,
habe soweit verstanden, aber wie kann z.b laufzeitverhalten O(2n) oder wie in der Aufgabe O(n log n) sein?
kannst du mir bitte einen beispiel geben? (in deinem beispiel ist es O(n) )

#6

Hallo Fragewurm,

habe soweit verstanden, aber wie kann z.b laufzeitverhalten
O(2n) oder wie in der Aufgabe O(n log n) sein?
kannst du mir bitte einen beispiel geben? (in deinem beispiel
ist es O(n) )

Klassisches Beispiel für O(log n), ist die Binärsuche in einer sortierten Liste.

MfG Peter(TOO)

#7

Hi,

Quicksort hat zum Beispiel im Mittel eine Laufzeit von O(n log(n)).
Siehe auch http://de.wikipedia.org/wiki/Quicksort

Grüsse,

Herb

#8

Allgemein kann man vielleicht sagen, dass man ein Laufzeitverhalten von O(2n) erwarten kann, wenn ein Algorithmus 2 Aktionen durchführt, die jeweils O(n) haben (oder täusche ich mich da? Mit den O’s hab’ ich offen gestanden nie wirklich rumgerechnet, evtl. höchstens mal im Studium und das ist schon etwas her… :wink: )

Bsp. (konstruiert): Ein Algorithmus, der 2 * Summe(1 bis n) ausrechnen soll.
Möglichkeit 1 (O(n)): s=0; für i=1 bis n {s = s+i}; s = s*2;
Möglichkeit 2 (O(2n)):s=0; für i=1 bis n {s = s+i}; für i=1 bis n {s = s+i}

Ein nicht konstruiertes Beispiel hab’ ich leider gerade nicht zur Hand…

Gruß,
Martin

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]