Sortierfunktionen nach asymptotischem Wachstum

35

Angenommen, ich habe zum Beispiel eine Liste von Funktionen

nloglog(n),2n,n!,n3,nlnn,

Wie sortiere ich sie asymptotisch, dh nach der durch definierten Beziehung?

fOgfO(g) ,

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

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 ( ).n+n,f(n)0

JAN
quelle
4
Da das OP nie zurückgekommen ist, entferne ich das lokalisierte Material und stelle daraus eine Referenzfrage.
Raphael

Antworten:

48

Wenn Sie strenge Beweise wollen, ist das folgende Lemma oft nützlich bzw. hilfreich. handlicher als die Definitionen.

c=limnf(n)g(n)

  • c=0 fo(g) ,
  • c(0,)fΘ(g) und
  • c=   fω(g) .

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:

  • Drücken Sie beide Funktionen als und vergleichen Sie die Exponenten. Wenn ihr Verhältnis zu oder tendiert , tut dies auch der ursprüngliche Quotient.e0
  • Allgemeiner: Wenn Sie eine konvexe, stetig differenzierbare und streng zunehmende Funktion so dass Sie Ihren Quotienten als umschreiben könnenh

    f(n)g(n)=h(f(n))h(g(n)) ,

    mit undgΩ(1)

    limnf(n)g(n)= ,

    dann

    limnf(n)g(n)= .

    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²!

  • Schauen Sie sich das diskrete Äquivalent Stolz – Cesàro an .
  • Wenn Fakultäten auftauchen, verwenden Sie die Stirling-Formel :

    n!2πn(ne)n

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

    (logn)αo(nβ) für alle .α,β>0

  • Reihenfolge der Polynome:

    nαo(nβ) für alle .α<β

  • Polynome wachsen langsamer als Exponentiale:

    nαo(cn) für alle und .αc>1


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 :

Mit wircs:=lim supnf(n)g(n)

  • 0cs<fO(g) und
  • cs=0fo(g) .

Mit wirci:=lim infnf(n)g(n)

  • 0<cifΩ(g) und
  • ci=fω(g) .

Außerdem,

  • 0<ci,cs<fΘ(g)gΘ(f) und
  • ci=cs=1fg .

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

Raphael
quelle
@Juho Nicht öffentlich, Afaik, aber es ist elementar, sich selbst zu schreiben; Berechnen Limit[f[n]/g[n], n -> Infinity]und Ausführen einer Fallunterscheidung.
Raphael
20

Ein weiterer Tipp: Manchmal macht das Anwenden einer monotonen Funktion (wie log oder exp) die Dinge klarer.

Suresh
quelle
5
Dies sollte sorgfältig durchgeführt werden: , aber 2 2 nO ( 2 n ) . 2nO(n)22nO(2n)
Shaull
2
Abgeordnet. Das Ding "Apply Monotone Function" scheint eine Art Folklore zu sein, die im Allgemeinen nicht funktioniert. Wir haben an ausreichenden Kriterien gearbeitet und mir das einfallen lassen, was ich in der letzten Überarbeitung meiner Antwort gepostet habe .
Raphael
17

Skiena bietet eine sortierte Liste der Dominanzbeziehungen zwischen den häufigsten Funktionen in seinem Buch The Algorithm Design Manual:

n!cnn3n2n1+ϵnlgnnn1/2
lg2nlgnlgnlglgnlglgnα(n)1

Hier bezeichnet α(n) die inverse Ackermann-Funktion .

Robert S. Barnes
quelle
Das ist eine seltsam spezifische Liste. Viele der Beziehungen (was auch immer genau bedeutet) können zu einer Handvoll allgemeinerer Lemmata zusammengefasst werden.
Raphael
Es ist seine Notation für eine Dominanzbeziehung.
Robert S. Barnes
11

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.

Dave Clarke
quelle
9
Sollten wir Vodoo wirklich empfehlen ?
Raphael
+1 für den Vorschlag, Diagramme der Funktionen zu zeichnen, obwohl die verknüpften Diagramme eher verwirrend sind, es sei denn, Sie wissen, was sie bedeuten.
Tsuyoshi Ito
1
Nehmen Sie eine Grafik als Hinweis darauf, was Sie möglicherweise beweisen möchten. Dieser Hinweis kann natürlich falsch sein.
gnasher729
8

nloglogn and 2n, the first two functions of n, to get the list started.

We use the property that n=2logn to rewrite the first expression as nloglogn=(2logn)loglogn=2lognloglogn. We could then proceed to use the definition to show that nloglogn=2lognloglogno(2n), since for any constant c>0, there is an n0 such that for nn0, c(nloglogn)=c(2lognloglogn)<2n.

Next, we try 3n. We compare it to 2n, the largest element we have placed so far. Since 3n=(2log3)n=2nlog3, we similarly show that 2no(3n)=o(2nlog3).

Etc.

Patrick87
quelle
2

Here a list from Wikipedia, The lower in the table the bigger complexity class;

NameRunning TimeConstant timeO(1)Inverse Ackermann timeO(a(n))Iterated logarithmic timeO(logn)Log-logarithmicO(nlogn)Logarithmic timeO(logn)Polylogarithmic timepoly(logn)Fractional powerO(nc),where 0<c<1Linear timeO(n)"n log star n" timeO(nlogn)Quasilinear timeO(nlogn)Quadratic timeO(n2)Cubic timeO(n3)Polynomial timepoly(n)=2O(logn)Quasi-polynomial time2O(poly(logn))Sub-exponential time (first definition)O(2nϵ),ϵ>0Sub-exponential time (second definition)2o(n)Exponential time(with linear exponent)2O(n)Exponential time2poly(n)Factorial timeO(n!)

note : poly(x)=xO(1)

kelalaka
quelle
1
Interessant auch, wie die Tabelle das suggeriert 2nLognO(n!). Während die Tabelle , die Sie verknüpfen , um etwas genau ist, verknüpft die man dort (und die Sie kopiert) etwa Komplexitätsklassen, das ist nicht eine hilfreiche Sache , hier zu mischen. Bei der Landau-Notation geht es nicht um "Zeit".
Raphael
1
I put this so the name of the complexity classes can be talked directly here. Yes, Landau is more about a specific type of algorithm in Cryptography.
Kelalaka
1
I object to some of @Raphael's views. I have been a mathematician and an instructor for many years. I believe, apart from proving those things, a big table like this increases people's intuition easily and greatly. And the names of the asymptotic classes help people remember and communicate a lot.
Apass.Jack
1
@ Apass.Jack In meiner Unterrichtserfahrung lernen viele Schüler auswendig, wenn sie einen Tisch erhalten, und können keine Funktion bestellen, die nicht in der Tabelle enthalten ist. Beachten Sie, wie dieser Effekt viele Fragen zum asymptotischen Wachstum zu erklären scheint, die auf dieser Site landen. Das heißt, wir werden natürlich Lemmata verwenden, die von der Tabelle impliziert werden, wenn es Beweise einfacher macht, aber das kommt, nachdem wir gelernt haben, wie man die Tabelle prüft . (Um diesen Punkt zu betonen, brauchen die Leute, die hierher kommen, keine Hilfe, um Dinge von einem Tisch zu lesen. Sie brauchen Hilfe, um Beziehungen zu beweisen .)
Raphael
1
@kelalaka "Ja, in Landau geht es mehr um eine bestimmte Art von Algorithmus in der Kryptographie." - das macht nicht mal Sinn. Die Landau-Notation ist eine Abkürzung zur Beschreibung der Eigenschaften mathematischer Funktionen. Es hat nichts mit Algorithmen zu tun, geschweige denn mit Kryptographie an sich.
Raphael