Angenommen, ich habe zum Beispiel eine Liste von Funktionen
Wie sortiere ich sie asymptotisch, dh nach der durch definierten Beziehung?
,
unter der Annahme, dass sie tatsächlich paarweise vergleichbar sind (siehe auch hier )? Die Definition von erscheint umständlich und es ist oft schwierig, die Existenz geeigneter Konstanten und zu beweisen .
Da es sich um Maßeinheiten für die Komplexität handelt, sind wir an asymptotischem Verhalten wie interessiert , und wir gehen davon aus, dass alle Funktionen nur nicht negative Werte annehmen ( ).
Antworten:
Wenn Sie strenge Beweise wollen, ist das folgende Lemma oft nützlich bzw. hilfreich. handlicher als die Definitionen.
Damit sollten Sie in der Lage sein, die meisten Funktionen der Algorithmusanalyse zu ordnen¹. Als Übung beweisen Sie es!
Natürlich muss man die Limits entsprechend berechnen können. Einige nützliche Tricks, um komplizierte Funktionen in grundlegende zu zerlegen, sind:
Allgemeiner: Wenn Sie eine konvexe, stetig differenzierbare und streng zunehmende Funktion so dass Sie Ihren Quotienten als umschreiben könnenh
mit undg∗∈Ω(1)
dann
Sehen Sie hier für einen strengen Beweis dieser Regel (in deutscher Sprache).
Betrachten Sie die Fortsetzung Ihrer Funktionen über den Real. Sie können jetzt die L'Hôpital-Regel anwenden. Achten Sie auf die Bedingungen²!
Wenn Fakultäten auftauchen, verwenden Sie die Stirling-Formel :
Es ist auch nützlich, einen Pool grundlegender Beziehungen zu führen, die Sie einmal nachweisen und häufig verwenden, wie z.
Logarithmen wachsen langsamer als Polynome, dh
Reihenfolge der Polynome:
Polynome wachsen langsamer als Exponentiale:
Es kann vorkommen, dass das obige Lemma nicht anwendbar ist, da das Limit nicht existiert (z. B. wenn Funktionen oszillieren). Betrachten Sie in diesem Fall die folgende Charakterisierung der Landau-Klassen mit Limes superior / inferior :
Überprüfen Sie hier und hier, ob Sie durch meine Notation verwirrt sind.
¹ Hinweis: Mein Kollege hat eine Mathematica-Funktion geschrieben, die dies für viele Funktionen erfolgreich ausführt, sodass das Lemma die Aufgabe wirklich auf mechanische Berechnung reduziert.
² Siehe auch hier .
quelle
Limit[f[n]/g[n], n -> Infinity]
und Ausführen einer Fallunterscheidung.Ein weiterer Tipp: Manchmal macht das Anwenden einer monotonen Funktion (wie log oder exp) die Dinge klarer.
quelle
Skiena bietet eine sortierte Liste der Dominanzbeziehungen zwischen den häufigsten Funktionen in seinem Buch The Algorithm Design Manual:
Hier bezeichnetα(n) die inverse Ackermann-Funktion .
quelle
Tipp: Zeichnen Sie Diagramme dieser Funktionen mit Wolfram Alpha , um ein Gefühl dafür zu bekommen, wie sie wachsen. Beachten Sie, dass dies nicht sehr genau ist, aber wenn Sie es für ausreichend große Zahlen versuchen, sollten Sie die vergleichenden Wachstumsmuster sehen. Dies ist natürlich kein Ersatz für einen Beweis.
Versuchen Sie beispielsweise: Zeichnen Sie ein Protokoll (log (n)) von 1 bis 10000 , um ein einzelnes Diagramm oder ein Diagrammprotokoll (log (n)) und ein Diagrammprotokoll (n) von 1 bis 10000 anzuzeigen , um einen Vergleich zu erhalten.
quelle
We use the property thatn=2logn to rewrite the first expression as nloglogn=(2logn)loglogn=2lognloglogn . We could then proceed to use the definition to show that nloglogn=2lognloglogn∈o(2n) , since for any constant c>0 , there is an n0 such that for n≥n0 , c(nloglogn)=c(2lognloglogn)<2n .
Next, we try3n . We compare it to 2n , the largest element we have placed so far. Since 3n=(2log3)n=2nlog3 , we similarly show that 2n∈o(3n)=o(2nlog3) .
Etc.
quelle
Here a list from Wikipedia, The lower in the table the bigger complexity class;NameConstant timeInverse Ackermann timeIterated logarithmic timeLog-logarithmicLogarithmic timePolylogarithmic timeFractional powerLinear time"n log star n" timeQuasilinear timeQuadratic timeCubic timePolynomial timeQuasi-polynomial timeSub-exponential time (first definition)Sub-exponential time (second definition)Exponential time(with linear exponent)Exponential timeFactorial timeRunning TimeO(1)O(a(n))O(log∗n)O(nlogn)O(logn)poly(logn)O(nc),where 0<c<1O(n)O(nlog∗n)O(nlogn)O(n2)O(n3)poly(n)=2O(logn)2O(poly(logn))O(2nϵ),ϵ>02o(n)2O(n)2poly(n)O(n!)
note :poly(x)=xO(1)
quelle