notación Big O - también conocido como el símbolo de Landau , en honor del matemático judío alemán, Edmund Landau - describe la tasa de crecimiento de una función , también conocido como el "orden", de ahí la mayúscula notación Big O "O" tiene por objeto medir el rendimiento de un algoritmo en sí , más que el hardware en el que se ejecuta el algoritmo. Una pieza de hardware puede ser más rápido o más lento que otra por un factor constante , por lo que todos los factores constantes son retirados de la notación O grande .
Constante Tiempo en el
Un algoritmo que siempre tiene más o menos el mismo tiempo para ejecutar , independientemente del tamaño de la entrada , se dice que tiene el tiempo de funcionamiento " constante " . En la notación O grande , este tipo de algoritmo es conocido como un algoritmo de "orden de 1 " y se denota por S ( 1 ) . Los ejemplos de ( 1 ) algoritmos o Incluir empujar o hacer estallar datos desde y hacia una pila de programación , y la recuperación de un único elemento de datos a partir de una matriz cuando se conoce su posición. Estos algoritmos sólo se realizan una serie de pasos , no importa lo grande que se convierte en la entrada.
Lineal Tiempo en el
un algoritmo cuya ejecución aumenta el tiempo de manera proporcional , o en forma lineal , que se dice con el tamaño de su entrada para tener tiempo funcionamiento " lineal " . En la notación O grande , este tipo de algoritmo se conoce como una " orden n " algoritmo y se denota por S ( n ) , lo que indica que el tiempo que toma para que el algoritmo para funcionar aumenta linealmente a medida que el número de elementos de datos , " n , " aumenta . Un ejemplo simple de un algoritmo O (n ) es un algoritmo que calcula el total de una lista de números ; se requiere una adición para cada elemento en la lista , por lo que el número de adiciones es el mismo que el número de elementos < br . >
cuadrático Tiempo en el
un algoritmo que se ejecuta el tiempo aumenta en un factor de n ^ 2 cuando el tamaño de los incrementos de entrada en un factor de "n " se dice que tener tiempo duración " cuadrática " . En la notación O grande , este tipo de algoritmo se conoce como una orden n ^ 2 algoritmo , o simplemente un algoritmo cuadrático , y se denota por S ( n ^ 2 ) . Ejemplos de algoritmos O ( n ^ 2 ) incluyen algoritmos de ordenación , como la inserción de clasificación y ordenamiento de burbuja , en la que duplicar el tamaño de la entrada cuadruplica el tiempo de ejecución .