Sind die Funktionen immer asymptotisch vergleichbar?

  • Wenn wir die Komplexität zweier Algorithmen vergleichen, ist es normalerweise der Fall, dass entweder $ f (n) = O (g (n)) $ oder $ g (n) = O (f ( n)) $ (möglicherweise beide), wobei $ f $ und $ g $ die Laufzeiten der beiden Algorithmen (zum Beispiel) sind.

    Ist dies immer der Fall? Das heißt, gilt immer mindestens eine der Beziehungen $ f (n) = O (g (n)) $ und $ g (n) = O (f (n)) $, das gilt für allgemeine Funktionen $ f $ $ g $? Wenn nicht, welche Annahmen müssen wir treffen und (warum) ist es in Ordnung, wenn wir über die Laufzeit von Algorithmen sprechen?

    16 May 2012
    Raphael
4 answers
  • Nicht jedes Funktionspaar ist mit der $ O (\ cdot) $ -Notation vergleichbar. Betrachten Sie die Funktionen $ f (n) = n $ und $$ g (n) = \ begin {cases} 1 & amp; \ text {wenn $ n $ ungerade ist}, \\\ n ^ 2 & amp; \ text {wenn $ n $ gerade ist}. \ end {cases} $$ Außerdem treten Funktionen wie $ g (n) $ tatsächlich als Laufzeiten von Algorithmen auf. Betrachten Sie den offensichtlichen Brute-Force-Algorithmus, um zu bestimmen, ob eine gegebene ganze Zahl $ n $ eine Primzahl ist:

     IsPrime(n):
      for i ← 2 to (n-1)
         if i·⌊n/i⌋ = n
            return False
      return True
      
    < Dieser Algorithmus erfordert $ \ Theta (1) $ - Arithmetikoperationen, wenn $ n $ gerade ist, $ O (\ sqrt {n}) $ - Operationen, wenn $ n $ zusammengesetzt ist, aber $ \ Theta (n) $ - Operationen, wenn $ n $ ist Primzahl. Daher ist dieser Algorithmus formal nicht vergleichbar mit einem Algorithmus, der $ \ sqrt {n} $ arithmetische Operationen für jeden $ n $ verwendet.

    Wenn wir Algorithmen analysieren, wollen wir meistens nur eine asymptotische Obergrenze der Form $ O (f (n)) $ für eine relativ einfache Funktion $ f $. Zum Beispiel würden die meisten Lehrbücher einfach (und richtig) melden, dass IsPrime (n) in arithmetischen Operationen $ O (n) $ ausgeführt wird. Typische Obergrenzenfunktionen sind Produkte von Exponentialen, Polynomen und Logarithmen (obwohl mehr exotische Bestien wie Fakultäten und iterated logarithms < auch gelegentlich auftauchen). Es ist nicht schwer zu beweisen, dass zwei dieser Funktionen vergleichbar sind.

    Siehe auch dieser MathOverflow-Frage .

    06 March 2018
    jm666
  • Von Wikipedia aus Definition der großen O-Notation:

    wenn und nur dann, wenn eine positive Konstante M wie für alle ausreichend große Werte von $ x $, $ f (x) $ sind höchstens M multipliziert mit $ g (x) $ im absoluten Wert. Das heißt, $ f (x) \ in O (g (x)) $ wenn und nur dann, wenn eine positive reelle Zahl $ M $ und eine reelle Zahl $ x_0 $ existiert, so dass

    $ | f (x) | & lt; = M | g (x) | \ quad \ text {for all} \; x & gt; x_0 $

    Was passiert bei Funktionen, die nicht konvergieren (zu einer Konstanten oder unendlich)?

    Schauen Sie sich die Funktionen $ f (x) = | xsin (x) | $ an, und $ g (x) = 10 $

    für jeden $ x_0 $ gibt es einige $ x & gt; x0 $, so dass $ x = k \ pi $, also $ f (x) = 0 $ - also für jedes $ M $ - $ Mf (x) & gt; g (x) $ ergibt false und $ g (x) \; \ not \ in O (f (x)) $

    Es ist jedoch leicht zu sehen, dass $ | xsin (x) | $ auch nicht durch eine Konstante begrenzt ist. für jeden $ M $, $ x_0 $ gibt es also einige $ x & gt; x_0 $, so dass $ f (x) & lt; Mg (x) $ ergibt ebenfalls false, und $ f (x) \ not \ in O (g (x)) $

    Hinweis: Zur Definition, wenn großes O dies zulässt eine maximale konstante Differenz zwischen $ Mf (x) $ und $ g (x) $, gilt dieselbe Idee mit $ g (x) = \ log (x) $

    11 May 2012
    Ryan FoxCade
  • Hier sind ein Paar monotoner Funktionen, die nicht asymptotisch vergleichbar sind. Dies ist relevant, da die meisten in der Praxis auftretenden Komplexitäten tatsächlich monoton sind.

    $$ f (x) = \ Gamma (\ lfloor x \ rfloor + 1) = \ lfloor x \ Boden! $$ $$ g (x) = \ Gamma (\ Boden x-1/2 \ Boden + 3/2) $$

    Hier ist $ \ Gamma $ ist die Gamma-Funktion . Die zweite Funktion ist speziell so aufgebaut, dass sie der Fakultät sehr ähnlich ist und an leicht versetzten Punkten in der Gamma-Funktion "abgetastet" wird. Die Funktionen kreuzen sich periodisch so, dass keine der beiden asymptotisch aneinander gebunden ist.

    16 October 2012
    Marcio Aguiar
  • Sei $ \ mathcal {L} $ die Klasse von Funktionen, die von der Identitätsfunktion und den Konstanten mit den folgenden Operationen erhalten werden: Addition, Subtraktion, Multiplikation, Division, Logarithmus und Exponential. Beispiel: $ \ exp (2 \ sqrt {\ log x + \ log \ log x}) / x ^ 2 $. Hardy bewies, dass für jeweils zwei Funktionen $ f, g \ in \ mathcal {L} $, die positiv sind und zur Unendlichkeit neigen, eine der folgenden Bedingungen zutrifft: $ f = o (g) $, $ f = \ omega (g ) $, $ f / g $ tendiert zu einer Konstanten. Siehe Seite 18 seines Buches "Orders of Infinity".

    Das Ergebnis ist, dass alle zwei "einfachen" Funktionen, die bei der Analyse des Algorithmus auftreten, vergleichbar sind . "Einfach" bedeutet hier, dass es keine Definition von Fällen gibt (abgesehen von endlich vielen Basisfällen), und es treten keine überraschenden Funktionen auf, wie z. B. die inverse Ackermann-Funktion, die manchmal in Laufzeiten auftritt.

    16 October 2012
    Brian