552 votos

Big O, ¿cómo lo calculas/aproximas?

La mayoría de las personas con un título en CS ciertamente sabrán lo que La gran O significa . Nos ayuda a medir cuán (in)eficiente es realmente un algoritmo y si sabes que en en qué categoría se encuentra el problema que estás tratando de resolver puedes averiguar si todavía es posible exprimir ese pequeño rendimiento extra. 1

Pero tengo curiosidad, ¿cómo usted calcular o aproximar la complejidad de sus algoritmos?

1 pero como dicen, no exageres, <a href="http://en.wikipedia.org/wiki/Optimization_%28computer_science%29#When_to_optimize">la optimización prematura es root de todo mal </a>y la optimización sin una causa justificada debería merecer también ese nombre.

1033voto

vz0 Puntos 11605

Soy profesor asistente en mi universidad local en el curso de Estructuras de Datos y Algoritmos. Haré lo que pueda para explicarlo aquí en términos simples, pero les advierto que este tema le toma a mis estudiantes un par de meses para finalmente comprenderlo. Pueden encontrar más información en el capítulo 2 del Estructuras de datos y algoritmos en Java libro.

No hay ningún procedimiento mecánico que puede ser usado para conseguir el BigOh.

Como un "libro de cocina", para obtener el BigOh a partir de un pedazo de código primero tienes que darte cuenta de que estás creando una fórmula matemática para contar cuántos pasos de cómputos se ejecutan dada una entrada de algún tamaño.

El propósito es simple: comparar los algoritmos desde un punto de vista teórico, sin necesidad de ejecutar el código. Cuanto menor sea el número de pasos, más rápido será el algoritmo.

Por ejemplo, digamos que tienes este pedazo de código:

int sum(int* data, int N) {
    int result = 0; // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i]; // 3
    }

    return result; // 4
}

Esta función devuelve la suma de todos los elementos del Array, y queremos crear una fórmula para contar el complejidad computacional de esa función:

Number_Of_Steps = f(N)

Así que tenemos f(N) una función para contar el número de pasos de cálculo. La entrada de la función es el tamaño de la estructura a procesar. Significa que esta función se llama tal como:

Number_Of_Steps = f(data.length)

El parámetro N toma el data.length valor. Ahora necesitamos la definición real de la función f() . Esto se hace a partir del código fuente, en el que cada línea interesante está numerada del 1 al 4.

Hay muchas maneras de calcular el BigOh. De aquí en adelante vamos a asumir que cada frase que no depende del tamaño de los datos de entrada toma una constante C numerando los pasos de computación.

Vamos a añadir el número individual de pasos de la función, y ni la declaración de la variable local ni la declaración de retorno dependen del tamaño de la data Arriba.

Eso significa que las líneas 1 y 4 tienen una cantidad de pasos C cada una, y la función es algo así:

f(N) = C + ??? + C

La siguiente parte es definir el valor de la for declaración. Recuerda que estamos contando el número de pasos de cálculo, lo que significa que el cuerpo de la declaración for se ejecuta N veces. Eso es lo mismo que sumar C , N veces:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

No hay una regla mecánica para contar cuántas veces se ejecuta el cuerpo del para, hay que contarlo mirando lo que hace el código. Para simplificar los cálculos, estamos ignorando las partes de inicialización, condición e incremento de las variables del for declaración.

Para conseguir el verdadero BigOh necesitamos el Análisis asintótico de la función. Esto se hace más o menos así:

  1. Quita todas las constantes C .
  2. De f() obtener el polinomio en su standard form .
  3. Dividir los términos del polinomio y clasificarlos por la tasa de crecimiento.
  4. Mantén el que se hace más grande cuando N enfoques infinity .

Nuestro f() tiene dos términos:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Quitando todos los C constantes y partes redundantes:

f(N) = 1 + N ^ 1

Ya que el último término es el que se hace más grande cuando f() se acerca al infinito (piense en límites ) este es el argumento de BigOh, y el sum() función tiene un BigOh de:

O(N)

Hay algunos trucos para resolver algunos trucos: usar summations siempre que puedas. Hay algunos útiles identidades sumarias ya se ha demostrado que es correcto.

Como otro ejemplo, este código puede ser fácilmente resuelto usando sumas:

// A
for (i = 0; i < 2*n; i += 2) { // 1
    for (j=n; j > i; j--) { // 2
        foo(); // 3
    }
}

La primera cosa que necesitabas que te pidieran es la orden de ejecución de foo() . Mientras que lo habitual es ser O(1) tienes que preguntarle a tus profesores sobre ello. O(1) significa (casi, en su mayoría) constante C independientemente del tamaño N .

El for La declaración de la sentencia número uno es difícil. Mientras que el índice termina en 2 * N el incremento se hace de dos en dos. Eso significa que el primer for sólo se ejecuta N pasos, y tenemos que dividir la cuenta por dos.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

El número de la frase dos es aún más complicado ya que depende del valor de i . Echa un vistazo: el índice i toma los valores: 0, 2, 4, 6, 8, ..., 2 * N, y el segundo for ser ejecutado: N veces la primera, N - 2 la segunda, N - 4 la tercera... hasta la etapa N / 2, en la que la segunda for nunca se ejecuta.

En la fórmula, eso significa:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

De nuevo, estamos contando el número de pasos . Y por definición, toda suma debe comenzar siempre en uno y terminar en un número mayor o igual que uno.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Estamos asumiendo que foo() es O(1) y toma C pasos.)

Tenemos un problema aquí: cuando i toma el valor N / 2 + 1 hacia arriba, la suma interna termina en un número negativo! Eso es imposible y está mal. Tenemos que dividir la suma en dos, siendo el punto central el momento i toma N / 2 + 1 .

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Desde el momento crucial i > N / 2 el interior no se ejecutará, y estamos asumiendo una constante complejidad de ejecución C en su cuerpo.

Ahora las sumas pueden ser simplificadas usando algunas reglas de identidad:

  1. Suma(w de 1 a N)( C ) = N * C
  2. Suma(w de 1 a N)( A (+/-) B ) = Suma(w de 1 a N)( A ) (+/-) Suma(w de 1 a N)( B )
  3. Suma(w de 1 a N)( w * C ) = C * Suma(w de 1 a N)( w ) (C es una constante, independiente de w )
  4. Suma(w de 1 a N)( w ) = (w * (w + 1)) / 2

Aplicando algo de álgebra:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

Y el BigOh es:

O(N ^ 2)

173voto

DShook Puntos 5361

Big O da el límite superior de la complejidad temporal de un algoritmo. Suele utilizarse junto con el procesamiento de conjuntos de datos (listas), pero puede utilizarse en otros lugares.

Algunos ejemplos de cómo se usa en el código C.

Digamos que tenemos un conjunto de n elementos

int array[n];

Si quisiéramos acceder al primer elemento del Array este sería O(1) ya que no importa cuán grande sea el Array, siempre toma el mismo tiempo constante para obtener el primer elemento.

x = array[0];

Si quisiéramos encontrar un número en la lista:

for(int i = 0; i < n; i++){    if(array[i] == numToFind){ return i; }}

Esto sería O(n) ya que como mucho tendríamos que buscar en toda la lista para encontrar nuestro número. El Big-O sigue siendo O(n), aunque podríamos encontrar nuestro número en el primer intento y recorrer el bucle una vez porque Big-O describe el límite superior de un algoritmo (omega es para el límite inferior y theta es para el límite superior).

Cuando lleguemos a los bucles anidados:

for(int i = 0; i < n; i++){    for(int j = i; j < n; j++){        array[j] += 2;    }}

Esto es O(n^2) ya que para cada pasada del bucle exterior ( O(n) ) tenemos que volver a recorrer toda la lista para que las n se multipliquen dejándonos con n al cuadrado.

Esto es apenas rascar la superficie, pero cuando se llega a analizar algoritmos más complejos, entran en juego matemáticas complejas que implican pruebas. Espero que esto te familiarice con lo básico, al menos.

62voto

Giovanni Galbo Puntos 8139

Si bien es útil saber cómo calcular el tiempo de Big O para su problema particular, conocer algunos casos generales puede ayudar mucho a tomar decisiones en su algoritmo.

Aquí están algunos de los casos más comunes, sacados de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O(1) - Determinar si un número es par o impar; usando una tabla de búsqueda de tamaño constante o una tabla de hash

O(logn) - Encontrar un elemento en una matriz ordenada con una búsqueda binaria

O(n) - Encontrar un artículo en una lista no clasificada; añadir dos números de n dígitos

O(n^2) - Multiplicar dos números de n dígitos por un simple algoritmo; sumar dos matrices de n×n; clasificación de burbujas o clasificación de inserción

O(n^3) - Multiplicando dos matrices n×n por un simple algoritmo

O(c^n) - Encontrar la solución (exacta) al problema del vendedor viajero usando programación dinámica; determinar si dos afirmaciones lógicas son equivalentes usando fuerza bruta

O(n!) - Resolver el problema del vendedor viajero a través de la búsqueda de fuerza bruta

O(n^n) - A menudo se utiliza en lugar de O(n!) para derivar fórmulas más simples para la complejidad asintótica

30voto

OysterD Puntos 2698

Pequeño recordatorio: la notación "O grande" se usa para denotar asintótica complejidad (es decir, cuando el tamaño del problema crece hasta el infinito), y esconde una constante.

Esto significa que entre un algoritmo en O(n) y uno en O(n^2), el más rápido no siempre es el primero (aunque siempre existe un valor de n tal que para problemas de tamaño >n, el primer algoritmo es el más rápido).

Note que la constante oculta depende en gran medida de la implementación!

Además, en algunos casos, el tiempo de ejecución no es una función determinante del "tamaño" n de la entrada. Tomemos como ejemplo la clasificación mediante quicksort: el tiempo necesario para clasificar una matriz de n elementos no es una constante sino que depende de la configuración inicial de la matriz; existen diferentes complejidades temporales: el peor caso (normalmente el más sencillo de averiguar, aunque no siempre muy significativo), el caso medio (normalmente mucho más difícil de averiguar :-( ).

Una buena introducción es 'An Introduction to the Analysis of Algorithms' de R. Sedgewick y P. Flajolet.

Como dices, "la optimización prematura es root de todo mal"... y (si es posible) el perfil siempre debe ser usado cuando se optimiza el código. Incluso puede ayudarte a determinar la complejidad de tus algoritmos.

21voto

Marcelo Cantos Puntos 91211

Si su costo es un polinomio, sólo mantenga el término más alto, sin su multiplicador. Por ejemplo..:

O((n/2 + 1)*(n/2)) = O(n) 2 /4 + n/2) = O(n 2 /4) = O(n) 2 )

Esto no funciona para las series infinitas, claro está. No hay una receta única para el caso general, aunque para algunos casos comunes, se aplican las siguientes desigualdades:

O(log N ) < O( N ) < O( N log N ) < O( N 2 ) < O( N k ) < O(e) n ) < O( n !)

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X