programm Speicher Algorithmus Professor komplex Algorithmen Komplexität

Komplexität von Algorithmen

Von: , Frage gestellt am Mo, 20. Mär 2000

Hallo, gibt es eigentlich eine Regel wie die Komplexität von Algorithmen anzugeben ist?

Mein Professor in Programmieren schert sich wenig um Konstanten, einen Algorithmus der Art

for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
...
}
}

gibt er eine Komplexität von O(n).
Der Professor in Informatik würde jedoch sagen O(1/2*n)

Kann man sowas vernachlässigen? Wenn ein Algorithmus doppelt so schnell ist wie ein anderer ist das doch ein Unterschied...

Bruno

6 Antworten zu dieser Frage

1. Antwort von nach 4 Stunden hilfreich

   Re: Komplexität von Algorithmen

   Hallo, gibt es eigentlich eine Regel wie
   die Komplexität von Algorithmen anzugeben
   ist?
   
   Die gibt es, nämlich besagte "gross-Oh"-Notation bezeichnet eine obere asymptotische Schranke für die Funktion (oder den Algorithmus). Mein Professor in Programmieren schert
   sich wenig um Konstanten, einen
   Algorithmus der Art
   
   for (i = 0; i < n; i++)
   {
   for (j = i; j < n; j++)
   {
   ...
   }
   }
   
   gibt er eine Komplexität von O(n).
   Der Professor in Informatik würde jedoch
   sagen O(1/2*n)
   
   wieso O(n) ?
   n+(n-1)+(n-2) + ... + 1 = 0.5 * n * (n +1 )
   -> O(n*n)
   "gross-Oh" ist nun so definiert, dass Konstanten entfallen.
   Interessant wird die Komplexität bei exponentiellem Wachstum, wo Algorithmen nicht mehr effizient (oder effektiv ?) sind.
   Wenn man bedenkt, dass die Rechenleistung sich alle 18 Monate verdoppelt, kann man die Konstanten ruhig unter den Teppich kehren.
   
   steffen Kann man sowas vernachlässigen? Wenn ein
   Algorithmus doppelt so schnell ist wie
   ein anderer ist das doch ein
   Unterschied...
   
   Bruno
   

   • Antwort von nach 4 Stunden hilfreich

     Re^2: Komplexität von Algorithmen

     Ja klar, ich meinte natürlich
     
     O(n*n) bzw. O(1/2*n*n)
     
     Eine Konstante kann ja beispielsweise auch ein tausendstel sein.
     Also wäre ein tausendfach schnellerer Algorithmus gleich komplex???
     
     Bruno
     

     • Antwort von nach 8 Stunden hilfreich

       Re^3: Komplexität von Algorithmen

       Nach der Def. von O schon. Wenn man versucht zu abstrahieren, geht eben etwas Information verloren. Du kannst natürlich auch Taktzyklen (in Abh. von n) zählen, dann hast Du die korrekte Komplexität ;)
       
       steffen [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
       

       • Antwort von nach 16 Tagen hilfreich

         Re^4: Komplexität von Algorithmen

         So wie ich die geschichte kennt, gibt die koplexitet das Verhältnis des Zeitaufwaandes ewnn eine Meng X bearbeitet werden muss und zu der Menge 2X.
         Es gibt nun vrschiedene Möglichkeiten:
         - das verhätnis ist lienar(wie in deinem Fall)
         - logarithmisch (Quick-Sort)
         - exponetiat
         
         Dabei spielt es dann keine rolle ob du O(1/2i) oder O(i) hast. Ist I doppelt so gross ist der Zeitaufwand doppelt so gross. Das ist das einzige was man dabei wissen will.
         
         MfG
         Kiril §8-)
         

         • Antwort von nach 67 Tagen hilfreich

           Re^5: Komplexitt von Algorithmen

           Hallo alle beisamen!
           
           Leider habe ich diesen Thread jetzt erst gelesen, deshalb meine spaete Reaktion. Ich versuch mal zu motivieren wozu man das Komplexitaetszeugs braucht und was das soll:
           
           Die Gross-Oh Notation, von der Du Bruno hier sprichst, gibt eine OBERE Schranke fuer der Speicherplatz UND Rechenzeitaufwand eines Algorithmusses fuer HINREICHEND grosse Probleminstanzen eines Problems an.
           Man spricht auch von einer asympthotischen Aufwandsanschaetzung. Kleine Problemumfaenge werden also vernachlaessigt!
           Deshalb ist die Wachstumsordnung einer Funktion f(n) (n-Groesse des Problems, f - Funktion fuer Rechenzeit oder Speicherplatz)), die durch die Funktion beschrieben wird von besonderem Interesse.
           
           Konstanten wachsen mit dem Faktor 1, Polynome mit n^a (a ist eine Konstante), exponentielles Wachstum a^n, n!, n^n, .... .
           
           Man sagt: Probleme fuer die keine Algorithmen existieren, der Komplexitat man durch ein Polynom (n^a) beschreiben kann, lassen sich praktisch nur fuer sehr kleine Problemumfaenge loesen. Das heisst, man will die praktisch loesbaren von den unloesbaren Problemen trennen.
           
           Ein konstanter Faktor b fuer ein Polynom
           b * (n ^ a) ist in diesem Betrachtungsrahmen eigentlich irrelevant und wird in asymptotischen Aufwandsabschaetzungen vernachlaessigt, weil dieser Faktor unabhaengig von Programmiersprachen, Maschinen, Betriebssystemen und anderen diversersen, in der Praxis sehr wichigen Einflussgroessen nicht bestimmt werden kann!
           
           Der grosse Haken bei der ganzen Sache besteht darin, dass ein Polynom fuer kleine Problemgroessen exponentielles Wachstum bei weitem ueberschreiten kann. z.B. n=2
           
           n^100 = was sehr Grosses, 2^n = 4
           
           Ein weiteres Problem in der Gross-Oh-Notation besteht darin, dass sie nicht dicht ist. Es existieren ja beliebig viele obere Komplexitaetsschranken zu einem Algorithmus (Problem). Welches ist die, die am dichtesten an der eigentlichen Rechenzeit bzw. Speicherplatzaufwand liegt?
           
           
           Ich hoffe der ritt in die Komplexitaet von Algorithmen hilft Dir weiter Bruno.
           
           Wenn Du noch Fragen hast, denn stelle Sie nur weiter. Ich beschaeftige mich mit dem Zeugs von berufswegen. Empfehlen dazu kann ich als Einstiegsliteratur Ottmann/ Widmayer:Algorithmen und Datenstrukturen
           
           Tschuess Jan
           

     • Antwort von nach 8 Tagen hilfreich

       Re^3: Komplexität von Algorithmen

       Eine Konstante kann ja beispielsweise
       auch ein tausendstel sein.
       Also wäre ein tausendfach schnellerer
       Algorithmus gleich komplex???
       Es geht ja bei der O-Notation um asymptotisches Wachstum. Das heißt, wichtig sind nur sehr sehr große Werte von n. Setze n=10^100, dann braucht ein tausendfach schnellerer Algorithmus im Verhältnis auch nicht viel weniger Zeit. Wesentlich für Dein Beispiel O(n*n) ist, das der Aufwand der Berechnung quadratisch mit der Eingabelänge steigt.
       
       Bis dann...
       ...Sven
       

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!