Komplexität algorithmus
-
Hallo,
die Komplexität eines Algorithmus sein 10*n
Zu welcher Klasse gehört dieser Algorithmus ?
Zu linear oder quadratisch. Schließlich wächst er ab n=10 quadratisch
aber ich hab auch mal gelesen dass konstante Faktoren weggelassen werden ??
-
blurry333 schrieb:
Schließlich wächst er ab n=10 quadratisch
Nö.
aber ich hab auch mal gelesen dass konstante Faktoren weggelassen werden ??
Jo.
-
stimmt. Er wächst nur von n=10 quadratisch
dann nicht mehr Ich suche genau Formeln für den Rechenaufwand eines Algoritmus.
Zu welcher Komplexitätsklasse ein Algorithmus gehört hab ich schon.
Aber es gibt noch genauere Formeln. Kennt jemand eine Seite ?
-
blurry333 schrieb:
stimmt. Er wächst nur von n=10 quadratisch
dann nicht mehrEr wächst auch bei n=10 nicht quadratisch: Die zweite Ableitung von 10*n an der Stelle 10 ist 0, deswegen kein qadratisches Wachstum an n=10.
-
-
ich suche genaue Formeln.
z.b. Quicksort : 1.39 * N * ld N
die weiß ich zufällig.
Aber von anderen Sortieralgorithmen kenn ich die Formel nicht
-
blurry333 schrieb:
ich suche genaue Formeln.
z.b. Quicksort : 1.39 * N * ld N
die weiß ich zufällig.
Aber von anderen Sortieralgorithmen kenn ich die Formel nicht
Das ist höchstens die Anzahl an Vergleichen. Bei normalen Laufzeitabschätzungen bezieht man aber alle Operationen mit ein. Da das von der konkreten Architektur abhängt, kann man so allgemein keine Formel angeben.
-
für den Rechenaufwand hat man die O Notation .
Welche Notation gibt es für den Speicheraufwand ?
-
Die O-Notation sagt nur was über das asymptotische Wachstum von Funktionen, ob man damit den Rechenzeit-, Speicher- oder Bratwurstverbrauch angibt ist völlig egal.
-
Eine vorsortierte Zahlenmenge stellt für den Heapaufbau den worstcase dar.
Ich hab grad einen heap 1,2,3,4,5,6,7 aufgebaut.
ich brauchte dafür 10 Vergleiche und 12 Kopieraktionen.
der worst case für n=7 sagt beim heap sort aber folgendes aus.
n*log(n) = 5,91 ( log basis 10)
was bedeutet das jetzt. schließlich brauche ich doch 10 vergleiche und 12 kopieraktionen , aber nicht 5,91 ??
-
1.) y=10x* ist keine quadratische Funktion.
2.) O(n log n) sagt nichts ueber die tatsaechlichen Operationen aus, nur das asymptotische Verhalten. Es sagt auch nichts darueber aus, welche Basis der Logarithmus hat. Deswegen macht es auch keinen Sinn konkrete Zahlen einzusetzen.
-
Du kannst aber für deinen Sortieralgorithmus für irgendwelche n, z.b. n=7,10,20,50,100,150,200,... die Anzahl der Operationen (oder die Laufzeit oder dergleichen) bestimmen und dann plotten. In das selbe Bild malst du n*log(n) und du wirst sehen, dass die Kurven sehr ähnlich aussehen: Je größer n, desto mehr wird der Abstand nur noch ein konstanter Faktor sein.
-
n log n
gilt also nur für sehr große n ??
ist das dann die Summe aus Vergleiche und Kopieraktionen ?
z.B. n=1 Million
ergibt 6 Mio. Vergleiche + Kopieraktionen = 6 MIo ???
-
gilt also nur für sehr große n ??
Nein!
ist das dann die Summe aus Vergleiche und Kopieraktionen ?
Nein!
-
ich versteh gar nichts mehr.
die Formel muss doch für was gut sein.
in wikipedia steht heapsort braucht immer n* log n Operationen.
-
Im Prinzip sagt die Formel nicht viel mehr, als dass ein O(nlog n)-Algorithmus schneller ist als ein O(n²)- oder O(2^n)-Algorithmus, aber langsamer als O(n) oder gar O(1). Dabei wird der Unterschied mit zunehmenden n immer deutlicher.
Wobei das eher pauschal zu betrachten ist, für kleine n kann z.B. O(n²) auch mal langsamer sein als O(nlog n).
-
Mit dem Aufwand kann man eigentlich nur aabschätzten, wie lange ein Algorithmus brauchen wird, wenn man ihm die doppelte, dreifache oder 100 fache Menge an Daten vorwirft. Das ist wichtig, wenn man einen Algo mit wenigen Daten testet, er aber später Millionen von Daten verarbeiten soll.
for (int i = 0; i < n; i++) { array[i] = 7; }Wird bei doppelter Arraylänge(n doppelt so groß) doppelt solange brauchen. Deshalb O(n). Die Zeit wächst genauso schnell wie die das Array.
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { array[i]++; } }Dieser Algorithmus wird bei doppeltem n viemal solange brauchen, da es zwei verschachtelte Schleifen sind => O(n^2)
In beiden Fällen entspricht das O(...) der anzahl der Operationen, jedoch läuft auch dieser Algo in O(n)for (int i = 0; i < n; i++) { array[i] = 7; array2[i] = 9; }Obwohl er doppelt soviele Operationen durchführt. Aber wenn man n verdoppelt braucht er doppelt so lange.
!! Man kann deshalb noch keine exakte Zeitberechnug anstellen, da z.b. ein If in der Schleife die Laufzeit je nach array-werten verzögern könnte. Aber im Durchschnitt kann man sagen, dass ein Algo x-mal solange braucht bei y-facher Anzahl an Eingabedaten. => Für kleine n's ist man naturgemäß weit vom Durchschnitt entfernt, weswegen es "nur für große n's sinnvoll ist von Aufwand zu reden"