Notación O grande: definición y ejemplos

INSTITUTO POLITECNICO NACIONAL                 UNIDAD PROFESIONAL INTERDICIPLINARIA DE INGENIERIA Y CIENCIAS SOCIALES Y ADMINISTRATIVAS[pic 1][pic 2]

ESTRUCTURA Y REPRESENTACION DE DATOS

ALEJANDRE RIVERA GERARDO ADONAY

2020600048

1CM21

Notación O grande: definición y ejemplos

La notación Big O es una forma conveniente de describir qué tan rápido está creciendo una función.

Definición

Cuando calculamos la complejidad temporal  T ( n ) de un algoritmo, raramente obtenemos un resultado exacto, solo una estimación. Eso está bien, en ciencias de la computación generalmente solo estamos interesados ​​en qué tan rápido crece T ( n ) en función del tamaño de entrada  n .

Por ejemplo, si un algoritmo incrementa cada número en una lista de longitud  n , podríamos decir: "Este algoritmo se ejecuta en tiempo O ( n ) y realiza el trabajo O (1) para cada elemento".

Aquí está la definición matemática formal de Big O.

Sean T ( n ) yf ( n ) dos funciones positivas. Escribimos T ( n ) ∊  O (f ( n )) y decimos que T ( n ) tiene un orden de f ( n ), si hay constantes positivas M y n₀ tales que T ( n ) ≤ M · f ( n ) para todos  n  ≥ n₀.

Este gráfico muestra una situación en la que se cumplen todas las condiciones de la definición.

[pic 3]

En esencia:

T ( n ) ∊  O (f ( n )) significa que T ( n ) no crece más rápido que f ( n ).

Tiempo constante

Comencemos con el ejemplo más simple posible: T ( n ) ∊  O (1) .

Según la definición, esto significa que hay constantes M y n₀ tales que T ( n ) ≤ M cuando n  ≥ n₀. En otras palabras, T ( n ) ∊  O (1) significa que T ( n ) es más pequeño que alguna constante fija, cuyo valor no se indica, para todos los valores suficientemente grandes de  n .

Se dice que un algoritmo con T ( n ) ∊  O (1) tiene una complejidad de tiempo constante .

Tiempo lineal

En el artículo Complejidad de tiempo , observamos un algoritmo con complejidad T ( n ) =  n  -1. Usando la notación Big O esto se puede escribir como T ( n ) ∊  O ( n ) . (Si

elegimos M = 1 y n₀ = 1, entonces T ( n ) =  n  - 1 ≤ 1 · n cuando n  ≥ 1.)

Se dice que un algoritmo con T ( n ) ∊  O ( n ) tiene una complejidad de tiempo lineal .

Tiempo cuadrático

El segundo algoritmo en la complejidad Tiempo artículo tenía tiempo complejidad T ( n ) =  n 2 /2 -  n / 2. Con la notación Big O, esto se convierte en T ( n ) ∊  O ( n 2 ) , y decimos que el algoritmo tiene una complejidad de tiempo cuadrática .

Notación descuidada

La notación T ( n ) ∊  O (f ( n )) se puede usar incluso cuando f ( n ) crece mucho más rápido que T ( n ). Por ejemplo, podemos escribir T ( n ) =  n  - 1 ∊ O ( n 2 ). Esto es cierto, pero no muy útil.

Notación Ω y Θ

Big Omega se usa para dar un límite inferior para el crecimiento de una función. Se define de la misma manera que Big O, pero con el signo de desigualdad cambiado:

Sean T ( n ) yf ( n ) dos funciones positivas. Escribimos T ( n ) ∊ Ω (f ( n )) , y decimos que T ( n ) es un gran omega de f ( n ), si hay constantes positivas m y n₀ tales que T ( n ) ≥ m (f ( n )) para todos los  n  ≥ n₀.

...