Sind die Funktionen immer asymptotisch vergleichbar?

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

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

Nicht jedes Funktionspaar ist mit der Notation vergleichbar . Betrachte die Funktionen und Außerdem entstehen Funktionen wie tatsächlich als Laufzeiten von Algorithmen. Betrachten Sie den offensichtlichen Brute-Force-Algorithmus, um festzustellen, ob eine bestimmte Ganzzahl eine Primzahl ist:f ( n ) = n g ( n ) = { 1, wenn  n  ungerade ist , n 2, wenn  n gerade  ist . g ( n ) $O(\cdot)$$f(n) = n$

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

Dieser Algorithmus erfordert arithmetische Operationen, wenn n gerade ist, O ( $\Theta(1)$$n$Operationen, wennn zusammengesetztist, aberΘ(n)Operationen, wennnPrimzahl ist. Daher ist dieser Algorithmus formalnichtmit einem Algorithmus zu vergleichen, der$O(\sqrt{n})$$n$$\Theta(n)$$n$ arithmetische Operationen fürjedesn.$\sqrt{n}$ $n$

Die meiste Zeit, wenn wir Algorithmen analysieren, wollen wir nur eine asymptotische Obergrenze der Form für eine relativ einfache Funktion f . Zum Beispiel sind die meisten Lehrbücher würde einfach (und richtig) berichten , dass läuft in O ( n ) arithmetischen Operationen. Typische Funktionen der oberen Schranke sind Produkte von Exponentialen, Polynomen und Logarithmen (obwohl gelegentlich auch exotischere Tiere wie Fakultäten und iterierte Logarithmen auftauchen). Es ist nicht schwer zu beweisen, dass zwei solcher Funktionen vergleichbar sind.$O(f(n))$$f$IsPrime(n)$O(n)$

Siehe auch diese MathOverflow-Frage .

Aus Wikipedia, Definition der großen O-Notation:

wenn und nur wenn es eine positive Konstante M so ist , daß für alle hinreichend große Werte von , f ( x ) ist höchstens M multipliziert g ( x ) im absoluten Wert. Das heißt, f ( x ) ∈ O ( g ( x ) ) genau dann, wenn es eine positive reelle Zahl M und eine reelle Zahl x 0 gibt, so dass$x$$f(x)$$g(x)$$f(x) \in O(g(x))$$M$$x_0$

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

Was passiert mit Funktionen, die nicht konvergieren (gegen eine Konstante oder gegen unendlich)?

$f(x) = |xsin(x)|$$g(x) = 10$

$x_0$$x > x0$$x = k\pi$$f(x) = 0$$M$$Mf(x) > g(x)$$g(x) \; \not\in O(f(x))$

$|xsin(x)|$$M$$x_0$$x > x_0$$f(x) < Mg(x)$$f(x) \not\in O(g(x))$

$Mf(x)$$g(x)$$g(x) = \log(x)$

Hier ist ein Paar monotone Funktionen, die nicht asymptotisch vergleichbar sind. Dies ist relevant, da die meisten in der Praxis auftretenden Komplexitäten tatsächlich monoton sind.

$\Gamma$

$\mathcal{L}$$\exp(2\sqrt{\log x + \log\log x})/x^2$$f,g \in \mathcal{L}$$f = o(g)$$f = \omega(g)$$f/g$

Das Ergebnis ist , dass zwei „einfachen“ Funktionen in der Analyse von Algorithmen auftretenden sind vergleichbar. Hier bedeutet "einfach", dass es keine Definition nach Fällen gibt (außer endlich vielen Basisfällen) und keine überraschenden Funktionen auftreten, wie die inverse Ackermann-Funktion, die manchmal in Laufzeiten angegeben wird.