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
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 Artfor (i = 0; i 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
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
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]
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
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 §
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