¿Las funciones son siempre asintóticamente comparables?

Cuando comparamos la complejidad de dos algoritmos, generalmente ocurre que o (posiblemente ambos), donde y son los tiempos de ejecución (por ejemplo) de los dos algoritmos.$f(n) = O(g(n))$$g(n) = O(f(n))$$f$$g$

Este es siempre el caso? Es decir, ¿al menos una de las relaciones y siempre es válida, es decir, para las funciones generales , ? Si no, ¿qué suposiciones tenemos que hacer y (por qué) está bien cuando hablamos de tiempos de ejecución de algoritmos?$f(n) = O(g(n))$$g(n) = O(f(n))$$f$$g$

No todos los pares de funciones son comparables con la notación ; considerar las funciones y Además, funciones como realmente surgen como tiempos de ejecución de algoritmos. Considere el algoritmo obvio de fuerza bruta para determinar si un número entero es primo:f ( n ) = n g ( n ) = { 1 si  n  es impar , n 2 si  n  es par . g ( n ) $O(\cdot)$$f(n) = n$

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

Este algoritmo requiere operaciones aritméticas cuando es par, operaciones cuando es compuesto, pero operaciones cuando es primo. Por lo tanto, formalmente, este algoritmo es incomparable con un algoritmo que usa operaciones aritméticas para cada .n O ( $\Theta(1)$$n$nΘ(n)n$O(\sqrt{n})$$n$$\Theta(n)$$n$$\sqrt{n}$ $n$

La mayoría de las veces cuando analizamos algoritmos, solo queremos un límite superior asintótico de la forma para alguna función relativamente simple . Por ejemplo, la mayoría de los libros de texto simplemente reportarían (y correctamente) que se ejecuta en operaciones aritméticas . Las funciones de límite superior típicas son productos de exponenciales, polinomios y logaritmos (aunque las bestias más exóticas como factoriales y logaritmos iterativos también aparecen ocasionalmente). No es difícil demostrar que cualquiera de estas dos funciones sean comparables.f O ( n $O(f(n))$$f$IsPrime(n)$O(n)$

Vea también esta pregunta de MathOverflow .

De wikipedia, definición de notación O grande:

si y solo si hay una constante positiva M tal que para todos los valores suficientemente grandes de , es como máximo M multiplicado por en valor absoluto. Es decir, si y solo si existe un número real positivo y un número real tal quef ( x ) g ( x ) f ( x ) ∈ O ( g ( x ) ) M x $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$

¿Qué sucede para las funciones que no convergen (a una constante ni al infinito)?

Mire las funcionesyg ( x ) = $f(x) = |xsin(x)|$$g(x) = 10$

para cada , hay algo de , de modo que , por lo tanto , por lo que para cada - dará falso, y x > x 0 x = k π f ( x ) = 0 M M f ( x ) > g ( x ) g ( x $x_0$$x > x0$$x = k\pi$$f(x) = 0$$M$$Mf(x) > g(x)$$g(x) \; \not\in O(f(x))$

Sin embargo, es fácil ver quetampoco está limitado por ninguna constante, por lo tanto, para cada , , hay algo de modo que también dará falso, y$|xsin(x)|$$M$$x_0$$x > x_0$$f(x) < Mg(x)$$f(x) \not\in O(g(x))$

Nota: para la definición, si O grande que permite una diferencia máxima constante entre y , la misma idea se aplicará con$Mf(x)$$g(x)$$g(x) = \log(x)$

Aquí hay un par de funciones monotónicas que no son asintóticamente comparables. Esto es relevante porque la mayoría de las complejidades que surgen en la práctica son de hecho monótonas.

g ( x ) = Γ ( ⌊ x - 1 / 2 ⌋ + 3 / 2

Aquí, es la función gamma . La segunda función está especialmente construida para ser muy similar a la factorial, simplemente "muestreada" en puntos ligeramente desplazados en la función gamma. Las funciones se cruzan periódicamente entre sí de tal manera que ninguna está unida asintóticamente por la otra.$\Gamma$

Sea la clase de funciones obtenidas de la función de identidad y las constantes utilizando las siguientes operaciones: suma, resta, multiplicación, división, logaritmo y exponencial. Por ejemplo, exp ( 2 $\mathcal{L}$. Hardy demostró que por cada dos funcionesf,g∈Lque son positivas y tienden al infinito, una de las siguientes es verdadera:f=o(g),f=ω(g),f/gtiende a una constante. Ver página 18 de su libro "Órdenes del infinito".$\exp(2\sqrt{\log x + \log\log x})/x^2$$f,g \in \mathcal{L}$$f = o(g)$$f = \omega(g)$$f/g$

El resultado es que cualquiera de las dos funciones "simples" que ocurren en el análisis del algoritmo son comparables. Aquí "simple" significa que no hay definición por casos (aparte de muchos casos base finitos), y no aparecen funciones sorprendentes, como la función inversa de Ackermann que a veces figura en tiempos de ejecución.