Notación Landau

Las cinco clases del sistema de Landau describen el comportamiento asintótico, es decir, el comportamiento cuando el tamaño del problema tiende a infinito. Si bien esto puede parecer irrelevante para nuestros problemas del mundo real, muy finitos, la experiencia ha demostrado que el comportamiento de los algoritmos del mundo real refleja este comportamiento infinito en datos reales lo suficientemente bien como para ser de uso práctico.

O grande #

La notación Big O proporciona límites superiores para el crecimiento de funciones. Intuitivamente para f ∊ O(g), f crece como mucho tan rápido como g.

Formalmente f ∊ O(g) si y solo si hay un número positivo C y un número positivo ``n tal que para todos los números positivos m > n tenemos

C⋅g(m) > f(m).

Intuición de esta definición #

Intuición con respecto a C #

C es responsable de tragar factores constantes en las funciones. Si h es dos veces f, todavía tenemos h ∊ O(g) ya que C puede ser el doble de grande. Para esto hay dos razones:

• Notación más fácil: f ∊ O(n) es preferible a f ∊ O(7.39 n).
• Abstracción: Cualquier unidad de tiempo se traga en estas consideraciones porque no hay nada que ganar con ellas; difieren entre máquinas y los algoritmos pueden evaluarse sin eso. Dado que ‘C’ se traga factores constantes, las clases de complejidad permanecen iguales incluso en una máquina diez veces más rápida.

Intuición respecto a n #

n es responsable de tragarse las turbulencias iniciales. Un algoritmo puede tener una sobrecarga de inicialización que es enorme para entradas pequeñas, pero vale la pena a largo plazo. La elección de n permite entradas suficientemente grandes para obtener el foco mientras se ignora el estiramiento inicial.

Intuición con respecto a m #

m se extiende sobre todos los valores mayores que n - para formalizar la idea “desde n en adelante, esto se mantiene”.