Datei List Algorithmus Laufzeit element Algorithmen 10 Sek

laufzeit

Von: , Frage gestellt am Mo, 27. Jun 2005

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

7 Antworten zu dieser Frage

1. Antwort von nach einer Stunde 0 hilfreich

   Re: laufzeit

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

2. Antwort von nach 2 Stunden 0 hilfreich

   Re: laufzeit

   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
   

   • Antwort von nach 2 Tagen 0 hilfreich

     Re^2: laufzeit

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

     • Antwort von nach 2 Tagen 0 hilfreich

       Re^3: laufzeit

       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)
       

     • Antwort von nach 2 Tagen 0 hilfreich

       Re^3: laufzeit

       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
       

     • Antwort von nach 2 Tagen 0 hilfreich

       Re^3: laufzeit

       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... ;) )
       
       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]
       

3. Antwort von nach 8 Stunden 0 hilfreich

   Re: laufzeit

   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)
   

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!