Big O, ¿cómo se calcula / aproxima?

881

La mayoría de las personas con un grado en CS sin duda saber qué Big O significa . Nos ayuda a medir qué tan bien escala un algoritmo.

Pero tengo curiosidad, ¿cómo se calcula o aproximada de la complejidad de los algoritmos?

sven
fuente
44
Tal vez en realidad no necesite mejorar la complejidad de su algoritmo, pero al menos debería poder calcularlo para decidir ...
Xavier Nodet el
55
Encontré esta una explicación muy clara de Big O, Big Omega y Big Theta: xoax.net/comp/sci/algorithms/Lesson6.php
Sam Dutton
33
-1: suspiro, otro abuso de BigOh. BigOh es solo un límite superior asintótico y podría usarse para cualquier cosa y no solo está relacionado con CS. Hablar de BigOh como si hubiera un único no tiene sentido (un algoritmo de tiempo lineal también es O (n ^ 2), O (n ^ 3), etc.). Decir que nos ayuda a medir la eficiencia también es engañoso. Además, ¿qué pasa con el enlace a las clases de complejidad? Si todo lo que le interesa son las técnicas para calcular los tiempos de ejecución de los algoritmos, ¿cómo es eso relevante?
34
Big-O no mide la eficiencia; mide qué tan bien un algoritmo escala con el tamaño (podría aplicarse a otras cosas que no sean el tamaño también, pero eso es lo que probablemente nos interesa aquí), y eso solo asintóticamente, por lo que si no tiene suerte, un algoritmo con un tamaño "más pequeño" O puede ser más lento (si el Big-O se aplica a ciclos) que uno diferente hasta que alcance números extremadamente grandes.
ILoveFortran
44
Elegir un algoritmo en función de su complejidad Big-O suele ser una parte esencial del diseño del programa. Definitivamente no es un caso de 'optimización prematura', que en cualquier caso es una cita selectiva muy abusada.
Marqués de Lorne el

Respuestas:

1481

Haré todo lo posible para explicarlo aquí en términos simples, pero tenga en cuenta que este tema les toma a mis alumnos un par de meses para finalmente comprenderlo. Puede encontrar más información sobre el Capítulo 2 de las Estructuras de datos y Algoritmos en el libro de Java .


No hay ningún procedimiento mecánico que pueda usarse para obtener BigOh.

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

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

Por ejemplo, supongamos que tiene este 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 de la matriz, y queremos crear una fórmula para contar la complejidad computacional de esa función:

Number_Of_Steps = f(N)

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

Number_Of_Steps = f(data.length)

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

Hay muchas formas de calcular el BigOh. A partir de este momento, asumiremos que cada oración que no depende del tamaño de los datos de entrada toma un Cnúmero constante de pasos computacionales.

Vamos a agregar 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 datamatriz.

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

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

La siguiente parte es definir el valor de la fordeclaración. Recuerde que estamos contando el número de pasos computacionales, lo que significa que el cuerpo de la fordeclaración se ejecuta Nveces. Eso es lo mismo que sumar C, Ntiempos:

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

No existe una regla mecánica para contar cuántas veces forse ejecuta el cuerpo del elemento , debe contarlo observando qué hace el código. Para simplificar los cálculos, estamos ignorando la inicialización variable, la condición y las partes de incremento de la fordeclaración.

Para obtener el BigOh real, 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. Divida los términos del polinomio y ordénelos por la tasa de crecimiento.
  4. Mantenga el que se hace más grande cuando se Nacerca infinity.

El nuestro f()tiene dos términos:

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

Quitando todas las Cconstantes y partes redundantes:

f(N) = 1 + N ^ 1

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

O(N)

Hay algunos trucos para resolver algunos trucos: usa las sumas siempre que puedas.

Como ejemplo, este código se puede resolver fácilmente mediante sumaciones:

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

Lo primero que debe preguntarse es el orden de ejecución de foo(). Si bien lo habitual es O(1), debes preguntarle a tus profesores al respecto. O(1)significa (casi, en su mayoría) constante C, independiente del tamaño N.

La fordeclaración en la oración número uno es engañosa. Mientras el índice termina en 2 * N, el incremento se realiza en dos. Eso significa que el primero forsolo se ejecuta Npasos, y necesitamos dividir el conteo entre dos.

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

La oración número dos es aún más complicada ya que depende del valor de i. Eche un vistazo: el índice i toma los valores: 0, 2, 4, 6, 8, ..., 2 * N, y el segundo forse ejecuta: N veces el primero, N - 2 el segundo, N - 4 el tercero ... hasta la etapa N / 2, en la que el segundo fornunca se ejecuta.

En la fórmula, eso significa:

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

Nuevamente, estamos contando el número de pasos . Y, por definición, cada suma siempre debe comenzar 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 Cmedidas).

Tenemos un problema aquí: cuando illeva el valor N / 2 + 1hacia arriba, la suma interna termina en un número negativo. Eso es imposible y está mal. Necesitamos dividir la suma en dos, siendo el punto crucial que itoma el momento 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, lo interno forno se ejecutará, y estamos asumiendo una complejidad de ejecución C constante en su cuerpo.

Ahora las sumas se pueden simplificar 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) = (N * (N + 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²)
vz0
fuente
66
@arthur Eso sería O (N ^ 2) porque necesitaría un bucle para leer todas las columnas y uno para leer todas las filas de una columna en particular.
Abhishek Dey Das
@arthur: depende. Es O(n)dónde nestá el número de elementos, o O(x*y)dónde xy yson las dimensiones de la matriz. Big-oh es "relativo a la entrada", por lo que depende de cuál sea su entrada.
Mooing Duck
1
Gran respuesta, pero estoy realmente atascado. ¿Cómo se convierte Summation (i de 1 a N / 2) (N) en (N ^ 2/2)?
Parsa
2
@ParsaAkbari Como regla general, la suma (i de 1 a a) (b) es a * b. Esta es solo otra forma de decir b + b + ... (a veces) + b = a * b (por definición para algunas definiciones de multiplicación de enteros).
Mario Carneiro
No es tan relevante, pero solo para evitar confusiones, hay un pequeño error en esta oración: "el índice i toma los valores: 0, 2, 4, 6, 8, ..., 2 * N". El índice i en realidad sube a 2 * N - 2, el ciclo se detendrá entonces.
Albert
201

Big O da el límite superior para la complejidad temporal de un algoritmo. Por lo general, se usa junto con conjuntos de datos de procesamiento (listas), pero se puede usar en otros lugares.

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

Digamos que tenemos una matriz de n elementos

int array[n];

Si quisiéramos acceder al primer elemento de la matriz, este sería O (1) ya que no importa cuán grande sea la matriz, siempre se necesita 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 a lo sumo tendríamos que revisar toda la lista para encontrar nuestro número. Big-O sigue siendo O (n), aunque podríamos encontrar nuestro número el primer intento y ejecutar el ciclo 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 cerrado) .

Cuando llegamos a 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 externo (O (n)) tenemos que revisar toda la lista nuevamente para que las n se multipliquen dejándonos con n al cuadrado.

Esto apenas está rascando la superficie, pero cuando llega a analizar algoritmos más complejos, entran en juego las matemáticas complejas que involucran pruebas. Sin embargo, espero que esto te familiarice con lo básico al menos.

DShook
fuente
¡Gran explicación! Entonces, si alguien dice que su algoritmo tiene una complejidad O (n ^ 2), ¿significa que usará bucles anidados?
Navaneeth KN
2
En realidad no, cualquier aspecto que conduzca a n veces al cuadrado se considerará como n ^ 2
asyncwait
@NavaneethKN: No siempre verá el bucle anidado, ya que las llamadas a funciones pueden> O(1)funcionar por sí mismas. En las API estándar de C, por ejemplo, bsearches inherentemente O(log n), strlenes O(n)y qsortes O(n log n)(técnicamente no tiene garantías, y Quicksort en sí tiene la peor complejidad de caso O(n²), pero suponiendo que su libcautor no sea un imbécil, su complejidad de caso promedio es O(n log n)y usa una estrategia de selección de pivote que reduce las probabilidades de llegar al O(n²)caso). Y ambos bsearchy qsortpueden ser peores si la función de comparación es patológica.
ShadowRanger
95

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

Estos son algunos de los casos más comunes, extraídos de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1): determinar si un número es par o impar; utilizando una tabla de búsqueda de tamaño constante o una tabla hash

O (logn): búsqueda de un elemento en una matriz ordenada con una búsqueda binaria

O (n): búsqueda de un elemento en una lista sin clasificar; sumando dos números de n dígitos

O (n 2 ) - Multiplicar dos números de n dígitos por un algoritmo simple; sumando dos matrices n × n; tipo de burbuja o tipo de inserción

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

O (c n ): encontrar la solución (exacta) al problema del vendedor ambulante mediante la programación dinámica; determinar si dos afirmaciones lógicas son equivalentes usando la fuerza bruta

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

O (n n ): a menudo se usa en lugar de O (n!) Para obtener fórmulas más simples para la complejidad asintótica

Giovanni Galbo
fuente
¿Por qué no usar x&1==1para verificar la rareza?
Samy Bencherif
2
@SamyBencherif: Esa sería una forma típica de verificar (en realidad, solo probar x & 1sería suficiente, no es necesario verificar == 1; en C, x&1==1se evalúa como x&(1==1) gracias a la precedencia del operador , por lo que en realidad es lo mismo que probar x&1). Sin embargo, creo que estás leyendo mal la respuesta; Hay un punto y coma allí, no una coma. No dice que necesitaría una tabla de búsqueda para pruebas pares / impares, dice que tanto las pruebas pares / impares como la verificación de una tabla de búsqueda son O(1)operaciones.
ShadowRanger
No sé sobre el reclamo sobre el uso en la última oración, pero quien lo hace está reemplazando una clase por otra que no es equivalente. La clase O (n!) Contiene, pero es estrictamente más grande que O (n ^ n). La equivalencia real sería O (n!) = O (n ^ ne ^ {- n} sqrt (n)).
conditionalMethod
43

Pequeño recordatorio: la big Onotación se usa para denotar la complejidad asintótica (es decir, cuando el tamaño del problema crece hasta el infinito), y oculta 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).

¡Tenga en cuenta que la constante oculta depende mucho de la implementación!

Además, en algunos casos, el tiempo de ejecución no es una función determinista del tamaño n de la entrada. Tome la clasificación usando la clasificación rápida, por ejemplo: el tiempo necesario para ordenar una matriz de n elementos no es una constante, sino que depende de la configuración inicial de la matriz.

Hay diferentes complejidades de tiempo:

  • El peor de los casos (generalmente el más simple de resolver, aunque no siempre es muy significativo)
  • Caso promedio (generalmente mucho más difícil de entender ...)

  • ...

Una buena introducción es Introducción al análisis de algoritmos por R. Sedgewick y P. Flajolet.

Como usted dice, premature optimisation is the root of all evily (si es posible) la creación de perfiles siempre debe usarse al optimizar el código. Incluso puede ayudarlo a determinar la complejidad de sus algoritmos.

OysterD
fuente
3
En matemáticas, O (.) Significa un límite superior, y theta (.) Significa que tiene un límite superior e inferior. ¿Es la definición realmente diferente en CS, o es solo un abuso común de notación? Según la definición matemática, sqrt (n) es tanto O (n) como O (n ^ 2), por lo que no siempre es el caso de que haya alguna n después de la cual una función O (n) es más pequeña.
Douglas Zare
28

Al ver las respuestas aquí, creo que podemos concluir que la mayoría de nosotros sí aproximamos el orden del algoritmo al mirarlo y usar el sentido común en lugar de calcularlo con, por ejemplo, el método maestro como pensábamos en la universidad. Dicho esto, debo agregar que incluso el profesor nos animó (más adelante) a pensar en realidad en lugar de solo calcularlo.

También me gustaría agregar cómo se hace para funciones recursivas :

supongamos que tenemos una función como ( código de esquema ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

que calcula recursivamente el factorial del número dado.

El primer paso es tratar de determinar la característica de rendimiento para el cuerpo de la función solo en este caso, no se hace nada especial en el cuerpo, solo una multiplicación (o el retorno del valor 1).

Entonces el rendimiento para el cuerpo es: O (1) (constante).

Luego, intente determinar esto para la cantidad de llamadas recursivas . En este caso tenemos llamadas recursivas n-1.

Entonces, el rendimiento de las llamadas recursivas es: O (n-1) (el orden es n, ya que descartamos las partes insignificantes).

Luego junte los dos y tendrá el rendimiento para toda la función recursiva:

1 * (n-1) = O (n)


Peter , para responder a tus problemas planteados; el método que describo aquí en realidad maneja esto bastante bien. Pero tenga en cuenta que esto sigue siendo una aproximación y no una respuesta matemáticamente correcta completa. El método descrito aquí también es uno de los métodos que nos enseñaron en la universidad, y si mal no recuerdo, se utilizó para algoritmos mucho más avanzados que el factorial que utilicé en este ejemplo.
Por supuesto, todo depende de qué tan bien pueda estimar el tiempo de ejecución del cuerpo de la función y el número de llamadas recursivas, pero eso es igual de cierto para los otros métodos.

sven
fuente
Sven, no estoy seguro de que tu forma de juzgar la complejidad de una función recursiva vaya a funcionar para otras más complejas, como hacer una búsqueda / suma / algo de arriba a abajo en un árbol binario. Claro, podría razonar sobre un ejemplo simple y llegar a la respuesta. ¿Pero me imagino que tendrías que hacer algunas matemáticas para los recursivos?
Peteter
3
+1 para la recursividad ... También este es hermoso: "... incluso el profesor nos animó a pensar ..." :)
TT_
Sí, esto es muy bueno. Tiendo a pensarlo así, cuanto mayor es el término dentro de O (..), más trabajo estás haciendo / máquina. Pensarlo mientras se relaciona con algo podría ser una aproximación, pero también lo son estos límites. Simplemente le dicen cómo aumenta el trabajo a realizar cuando aumenta el número de entradas.
Abhinav Gauniyal
26

Si su costo es un polinomio, simplemente mantenga el término de orden más alto, sin su multiplicador. P.ej:

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

Esto no funciona para series infinitas, eso sí. No existe 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 !)

Marcelo Cantos
fuente
8
seguramente O (N) <O (NlogN)
jk.
22

Lo pienso en términos de información. Cualquier problema consiste en aprender un cierto número de bits.

Su herramienta básica es el concepto de puntos de decisión y su entropía. La entropía de un punto de decisión es la información promedio que le dará. Por ejemplo, si un programa contiene un punto de decisión con dos ramas, su entropía es la suma de la probabilidad de cada rama multiplicada por el log 2 de la probabilidad inversa de esa rama. Eso es lo que aprendes al ejecutar esa decisión.

Por ejemplo, una ifdeclaración que tiene dos ramas, ambas igualmente probables, tiene una entropía de 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Entonces su entropía es de 1 bit.

Suponga que está buscando una tabla de N elementos, como N = 1024. Ese es un problema de 10 bits porque log (1024) = 10 bits. Entonces, si puede buscarlo con declaraciones IF que tengan resultados igualmente probables, debería tomar 10 decisiones.

Eso es lo que obtienes con la búsqueda binaria.

Supongamos que está haciendo una búsqueda lineal. Miras el primer elemento y preguntas si es el que deseas. Las probabilidades son 1/1024 de lo que es, y 1023/1024 de lo que no es. La entropía de esa decisión es 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * aproximadamente 0 = aproximadamente .01 bit. ¡Has aprendido muy poco! La segunda decisión no es mucho mejor. Es por eso que la búsqueda lineal es tan lenta. De hecho, es exponencial en la cantidad de bits que necesita aprender.

Supongamos que estás haciendo indexación. Suponga que la tabla está ordenada previamente en muchos contenedores, y utiliza algunos de todos los bits en la clave para indexar directamente a la entrada de la tabla. Si hay 1024 contenedores, la entropía es 1/1024 * log (1024) + 1/1024 * log (1024) + ... para todos los 1024 resultados posibles. Esto es 1/1024 * 10 veces 1024 resultados, o 10 bits de entropía para esa operación de indexación. Es por eso que la búsqueda de indexación es rápida.

Ahora piensa en ordenar. Tienes N artículos y tienes una lista. Para cada elemento, debe buscar dónde va el elemento en la lista y luego agregarlo a la lista. Por lo tanto, la ordenación toma aproximadamente N veces el número de pasos de la búsqueda subyacente.

Por lo tanto, los tipos basados ​​en decisiones binarias que tienen resultados más o menos igualmente probables toman todos unos pasos O (N log N). Un algoritmo de clasificación O (N) es posible si se basa en la búsqueda de indexación.

He descubierto que casi todos los problemas de rendimiento algorítmico se pueden ver de esta manera.

Mike Dunlavey
fuente
Guau. ¿Tiene alguna referencia útil sobre esto? Siento que esto me ayuda a diseñar / refactorizar / depurar programas.
Jesvin Jose
3
@aitchnyu: Por lo que vale, escribí un libro que cubre ese y otros temas. Hace tiempo que se agotó, pero las copias cuestan un precio razonable. He intentado que GoogleBooks lo tome, pero en este momento es un poco difícil averiguar quién tiene los derechos de autor.
Mike Dunlavey
21

Vamos a empezar desde el principio.

En primer lugar, acepte el principio de que ciertas operaciones simples en los datos pueden realizarse a O(1)tiempo, es decir, en un tiempo que es independiente del tamaño de la entrada. Estas operaciones primitivas en C consisten en

  1. Operaciones aritméticas (p. Ej. + O%).
  2. Operaciones lógicas (p. Ej., &&).
  3. Operaciones de comparación (p. Ej., <=).
  4. Estructura de las operaciones de acceso (por ejemplo, indexación de matriz como A [i], o puntero siguiendo con el operador ->).
  5. Asignación simple como copiar un valor en una variable.
  6. Llamadas a funciones de biblioteca (p. Ej., Scanf, printf).

La justificación de este principio requiere un estudio detallado de las instrucciones de la máquina (pasos primitivos) de una computadora típica. Cada una de las operaciones descritas se puede hacer con un pequeño número de instrucciones de la máquina; a menudo solo se necesitan una o dos instrucciones. Como consecuencia, se pueden ejecutar varios tipos de declaraciones en C a O(1)tiempo, es decir, en una cantidad constante de tiempo independiente de la entrada. Estos simples incluyen

  1. Declaraciones de asignación que no implican llamadas a funciones en sus expresiones.
  2. Lee las declaraciones.
  3. Escriba declaraciones que no requieran llamadas a funciones para evaluar argumentos.
  4. Las declaraciones de salto rompen, continúan, pasan a, y devuelven la expresión, donde la expresión no contiene una llamada a la función.

En C, muchos bucles for se forman inicializando una variable de índice a algún valor e incrementando esa variable en 1 cada vez alrededor del bucle. El ciclo for termina cuando el índice alcanza algún límite. Por ejemplo, el bucle for

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

utiliza la variable de índice i. Incrementa i en 1 cada vez alrededor del ciclo, y las iteraciones se detienen cuando alcanzo n - 1.

Sin embargo, por el momento, concéntrese en la forma simple de for-loop, donde la diferencia entre los valores finales e iniciales, dividida por la cantidad por la cual se incrementa la variable de índice, nos dice cuántas veces damos la vuelta al ciclo . Ese recuento es exacto, a menos que haya formas de salir del ciclo a través de una declaración de salto; Es un límite superior en el número de iteraciones en cualquier caso.

Por ejemplo, el ciclo for itera ((n − 1) − 0)/1 = n − 1 times, ya que 0 es el valor inicial de i, n - 1 es el valor más alto alcanzado por i (es decir, cuando alcanzo n − 1, el ciclo se detiene y no ocurre ninguna iteración con i = n− 1), y 1 se agrega a i en cada iteración del bucle.

En el caso más simple, donde el tiempo pasado en el cuerpo del bucle es el mismo para cada iteración, podemos multiplicar el límite superior big-oh para el cuerpo por el número de veces alrededor del bucle . Estrictamente hablando, debemos agregar el tiempo O (1) para inicializar el índice del ciclo y el tiempo O (1) para la primera comparación del índice del ciclo con el límite , porque probamos una vez más de lo que hacemos. Sin embargo, a menos que sea posible ejecutar el ciclo cero veces, el tiempo para inicializar el ciclo y probar el límite una vez es un término de orden inferior que la regla de suma puede eliminar.


Ahora considere este ejemplo:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Sabemos que la línea (1) lleva O(1)tiempo. Claramente, damos la vuelta al bucle n veces, como podemos determinar restando el límite inferior del límite superior que se encuentra en la línea (1) y luego sumando 1. Como el cuerpo, línea (2), toma O (1) tiempo, podemos descuidar el tiempo para incrementar j y el tiempo para comparar j con n, los cuales también son O (1). Por lo tanto, el tiempo de ejecución de las líneas (1) y (2) es el producto de ny O (1) , que es O(n).

Del mismo modo, podemos limitar el tiempo de ejecución del bucle externo que consiste en las líneas (2) a (4), que es

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Ya hemos establecido que el ciclo de las líneas (3) y (4) toma tiempo O (n). Por lo tanto, podemos descuidar el tiempo O (1) para incrementar i y probar si i <n en cada iteración, concluyendo que cada iteración del bucle externo toma tiempo O (n).

La inicialización i = 0 del bucle externo y la prueba (n + 1) st de la condición i <n también requieren tiempo O (1) y pueden descuidarse. Finalmente, observamos que damos la vuelta al bucle externo n veces, tomando tiempo O (n) para cada iteración, dando un O(n^2)tiempo de ejecución total .


Un ejemplo más práctico.

ingrese la descripción de la imagen aquí

ajknzhol
fuente
¿Qué sucede si una instrucción goto contiene una llamada a función? Algo así como el paso 3: if (M.step == 3) {M = step3 (hecho, M); } paso4: if (M.step == 4) {M = step4 (M); } if (M.step == 5) {M = paso5 (M); ir al paso 3; } if (M.step == 6) {M = paso6 (M); ir al paso 4; } return cut_matrix (A, M); ¿Cómo se calcularía la complejidad entonces? ¿sería una suma o una multiplicación? considerando que el paso 4 es n ^ 3 y el paso 5 es n ^ 2.
Taha Tariq
14

Si desea estimar el orden de su código empíricamente en lugar de analizar el código, puede pegarse en una serie de valores crecientes de ny el tiempo de su código. Trace sus tiempos en una escala logarítmica. Si el código es O (x ^ n), los valores deben caer en una línea de pendiente n.

Esto tiene varias ventajas sobre solo estudiar el código. Por un lado, puede ver si está en el rango donde el tiempo de ejecución se acerca a su orden asintótico. Además, puede encontrar que algún código que pensó que era el orden O (x) es realmente el orden O (x ^ 2), por ejemplo, debido al tiempo dedicado a las llamadas a la biblioteca.

John D. Cook
fuente
Solo para actualizar esta respuesta: en.wikipedia.org/wiki/Analysis_of_algorithms , este enlace tiene la fórmula que necesita. Muchos algoritmos siguen una regla de potencia, si la suya lo hace, con 2 puntos de tiempo y 2 tiempos de ejecución en una máquina, podemos calcular la pendiente en un gráfico de registro-registro. Que es a = log (t2 / t1) / log (n2 / n1), esto me dio el exponente para el algoritmo en, O (N ^ a). Esto se puede comparar con el cálculo manual utilizando el código.
Christopher John
1
Hola, buena respuesta. Me preguntaba si conoce alguna biblioteca o metodología (por ejemplo, trabajo con python / R) para generalizar este método empírico, es decir, ajustar varias funciones de complejidad para aumentar el conjunto de datos de tamaño y descubrir cuál es relevante. Gracias
agenis
10

Básicamente, lo que surge el 90% del tiempo es solo analizar bucles. ¿Tiene bucles anidados simples, dobles y triples? El tiempo de ejecución de O (n), O (n ^ 2), O (n ^ 3).

Muy raramente (a menos que esté escribiendo una plataforma con una extensa biblioteca base (como, por ejemplo, .NET BCL o STL de C ++) encontrará algo que es más difícil que solo mirar sus bucles (para ver declaraciones, mientras que, ir a, etc ...)

Adán
fuente
1
Depende de los bucles.
kelalaka
8

La notación Big O es útil porque es fácil de trabajar y oculta complicaciones y detalles innecesarios (para alguna definición de innecesario). Una buena forma de resolver la complejidad de los algoritmos de divide y vencerás es el método del árbol. Supongamos que tiene una versión de clasificación rápida con el procedimiento de mediana, por lo que divide la matriz en submatrices perfectamente equilibradas cada vez.

Ahora construya un árbol correspondiente a todas las matrices con las que trabaja. En la raíz tiene la matriz original, la raíz tiene dos hijos que son las submatrices. Repita esto hasta que tenga matrices de elementos individuales en la parte inferior.

Como podemos encontrar la mediana en el tiempo O (n) y dividir la matriz en dos partes en el tiempo O (n), el trabajo realizado en cada nodo es O (k) donde k es el tamaño de la matriz. Cada nivel del árbol contiene (como máximo) toda la matriz, por lo que el trabajo por nivel es O (n) (los tamaños de las submatrices suman n, y dado que tenemos O (k) por nivel podemos sumar esto) . Solo hay niveles de registro (n) en el árbol ya que cada vez que reducimos a la mitad la entrada.

Por lo tanto, podemos limitar la cantidad de trabajo por O (n * log (n)).

Sin embargo, Big O esconde algunos detalles que a veces no podemos ignorar. Considere calcular la secuencia de Fibonacci con

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

y supongamos que a y b son BigIntegers en Java o algo que puede manejar números arbitrariamente grandes. La mayoría de la gente diría que este es un algoritmo O (n) sin parpadear. El razonamiento es que tiene n iteraciones en el bucle for y O (1) funciona en el lado del bucle.

Pero los números de Fibonacci son grandes, el enésimo número de Fibonacci es exponencial en n, por lo que solo almacenarlo tomará el orden de n bytes. Realizar la suma con enteros grandes requerirá O (n) cantidad de trabajo. Entonces, la cantidad total de trabajo realizado en este procedimiento es

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

¡Entonces este algoritmo se ejecuta en tiempo cuadrádico!


fuente
1
No debería importarle cómo se almacenan los números, no cambia que el algoritmo crezca en un límite superior de O (n).
mikek3332002
8

En general, creo que es menos útil, pero en aras de la exhaustividad también hay un Big Omega Ω , que define un límite inferior en la complejidad de un algoritmo, y un Big Theta Θ , que define tanto un límite superior como un límite inferior.

Martín
fuente
7

Divide el algoritmo en partes para las que conoces la gran notación O y combínalas a través de grandes operadores O. Esa es la única manera que sé.

Para obtener más información, consulte la página de Wikipedia sobre el tema.

Lasse V. Karlsen
fuente
7

Familiaridad con los algoritmos / estructuras de datos que uso y / o análisis rápido de anidación de iteración. La dificultad es cuando llama a una función de biblioteca, posiblemente varias veces; a menudo puede no estar seguro de si llama a la función innecesariamente a veces o qué implementación están utilizando. Tal vez las funciones de la biblioteca deberían tener una medida de complejidad / eficiencia, ya sea Big O o alguna otra métrica, que esté disponible en la documentación o incluso en IntelliSense .

Matt Mitchell
fuente
6

En cuanto a "cómo se calcula" Big O, esto es parte de la teoría de la complejidad computacional . Para algunos (muchos) casos especiales, puede venir con algunas heurísticas simples (como el conteo de bucles multiplicadores para bucles anidados), especialmente. cuando lo único que desea es una estimación de límite superior, y no le importa si es demasiado pesimista, lo que supongo es probablemente de lo que se trata su pregunta.

Si realmente desea responder a su pregunta para cualquier algoritmo, lo mejor que puede hacer es aplicar la teoría. Además del análisis simplista del "peor de los casos", he encontrado que el análisis Amortized es muy útil en la práctica.

Suma
fuente
6

Para el primer caso, el bucle interno se ejecuta n-iveces, por lo que el número total de ejecuciones es la suma para ipasar de 0a n-1(porque menor que, no menor o igual) de n-i. Llegas finalmente n*(n + 1) / 2, entonces O(n²/2) = O(n²).

Para el segundo bucle, iestá entre0 e nincluido para el bucle externo; entonces el bucle interno se ejecuta cuando jes estrictamente mayor que n, lo que es imposible.

Emmanuel
fuente
5

Además de utilizar el método maestro (o una de sus especializaciones), pruebo mis algoritmos experimentalmente. Esto no puede probar que se logre una clase de complejidad particular, pero puede garantizar que el análisis matemático sea apropiado. Para ayudar con esta garantía, utilizo herramientas de cobertura de código junto con mis experimentos, para asegurarme de que estoy ejercitando todos los casos.

Como un ejemplo muy simple, digamos que quería hacer una verificación de la cordura en la velocidad de la ordenación de la lista del marco .NET. Puede escribir algo como lo siguiente, luego analizar los resultados en Excel para asegurarse de que no excedan una curva n * log (n).

En este ejemplo, mido el número de comparaciones, pero también es prudente examinar el tiempo real requerido para cada tamaño de muestra. Sin embargo, debe ser aún más cuidadoso de que solo mida el algoritmo y no incluya artefactos de su infraestructura de prueba.

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);
Eric
fuente
4

No olvide permitir también las complejidades del espacio que también pueden ser motivo de preocupación si uno tiene recursos de memoria limitados. Entonces, por ejemplo, puede escuchar que alguien quiere un algoritmo de espacio constante, que es básicamente una forma de decir que la cantidad de espacio ocupado por el algoritmo no depende de ningún factor dentro del código.

A veces, la complejidad puede venir de cuántas veces se llama algo, con qué frecuencia se ejecuta un bucle, con qué frecuencia se asigna la memoria, y así sucesivamente es otra parte para responder a esta pregunta.

Por último, la O grande puede usarse para el peor de los casos, el mejor de los casos y los casos de amortización, donde generalmente es el peor de los casos que se utiliza para describir qué tan malo puede ser un algoritmo.

JB King
fuente
4

Lo que a menudo se pasa por alto es el comportamiento esperado de sus algoritmos. No cambia el Big-O de su algoritmo , pero se relaciona con la afirmación "optimización prematura ..."

El comportamiento esperado de su algoritmo es, muy tonto, qué tan rápido puede esperar que su algoritmo funcione en los datos que es más probable que vea.

Por ejemplo, si está buscando un valor en una lista, es O (n), pero si sabe que la mayoría de las listas que ve tienen su valor por adelantado, el comportamiento típico de su algoritmo es más rápido.

Para realmente precisarlo, debe ser capaz de describir la distribución de probabilidad de su "espacio de entrada" (si necesita ordenar una lista, ¿con qué frecuencia se va a ordenar esa lista? ¿Con qué frecuencia se invierte totalmente? a menudo se clasifica principalmente?) No siempre es factible que lo sepas, pero a veces lo sabes.

Baltimark
fuente
4

gran pregunta!

Descargo de responsabilidad: esta respuesta contiene declaraciones falsas, vea los comentarios a continuación.

Si está utilizando Big O, está hablando del peor de los casos (más sobre lo que eso significa más adelante). Además, hay capital theta para el caso promedio y una gran omega para el mejor caso.

Consulte este sitio para obtener una hermosa definición formal de Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) significa que hay constantes positivas c y k, de modo que 0 ≤ f (n) ≤ cg (n) para todo n ≥ k. Los valores de c y k deben ser fijos para la función f y no deben depender de n.


Ok, entonces, ¿a qué nos referimos con las complejidades de "mejor caso" y "peor de los casos"?

Esto probablemente se ilustra más claramente a través de ejemplos. Por ejemplo, si estamos utilizando la búsqueda lineal para encontrar un número en una matriz ordenada, entonces el peor de los casos es cuando decidimos buscar el último elemento de la matriz, ya que esto tomaría tantos pasos como elementos hay en la matriz. El mejor caso sería cuando buscamos el primer elemento ya que terminaríamos después de la primera verificación.

El punto de todas estas complejidades de caso adjetivo es que estamos buscando una forma de graficar la cantidad de tiempo que un programa hipotético se ejecuta hasta su finalización en términos del tamaño de variables particulares. Sin embargo, para muchos algoritmos, puede argumentar que no hay una sola vez para un tamaño particular de entrada. Tenga en cuenta que esto contradice el requisito fundamental de una función, cualquier entrada no debe tener más de una salida. Así que se nos ocurren múltiples funciones para describir la complejidad de un algoritmo. Ahora, aunque buscar una matriz de tamaño n puede tomar diferentes cantidades de tiempo dependiendo de lo que esté buscando en la matriz y dependiendo proporcionalmente de n, podemos crear una descripción informativa del algoritmo usando el mejor caso, el caso promedio , y las peores clases de caso.

Lo siento, está tan mal escrito y carece de mucha información técnica. Pero con suerte hará que sea más fácil pensar en las clases de complejidad del tiempo. Una vez que se sienta cómodo con estos, se convierte en una simple cuestión de analizar su programa y buscar cosas como bucles for que dependen del tamaño de la matriz y el razonamiento basado en sus estructuras de datos, qué tipo de entrada daría lugar a casos triviales y qué entrada resultaría en el peor de los casos.

Samy Bencherif
fuente
1
Esto es incorrecto. Big O significa "límite superior", no el peor de los casos.
Samy Bencherif
1
Es un error común pensar que big-O se refiere al peor de los casos. ¿Cómo se relacionan O y Ω con el peor y el mejor caso?
Bernhard Barker
1
Esto es engañoso. Big-O significa límite superior para una función f (n). Omega significa límite inferior para una función f (n). No está en absoluto relacionado con el mejor caso o el peor de los casos.
Tasneem Haider
1
Puede usar Big-O como límite superior para el mejor o el peor de los casos, pero aparte de eso, sí, no hay relación.
Samy Bencherif
2

No sé cómo resolver esto programáticamente, pero lo primero que hace la gente es que muestreamos el algoritmo para ciertos patrones en la cantidad de operaciones realizadas, digamos 4n ^ 2 + 2n + 1 tenemos 2 reglas:

  1. Si tenemos una suma de términos, se mantiene el término con la mayor tasa de crecimiento, con otros términos omitidos.
  2. Si tenemos un producto de varios factores, se omiten factores constantes.

Si simplificamos f (x), donde f (x) es la fórmula para el número de operaciones realizadas, (4n ^ 2 + 2n + 1 explicado anteriormente), obtenemos el valor de O grande [O (n ^ 2) en este caso]. Pero esto tendría que explicar la interpolación de Lagrange en el programa, que puede ser difícil de implementar. ¿Y si el verdadero valor de O grande fuera O (2 ^ n) y pudiéramos tener algo como O (x ^ n), por lo que este algoritmo probablemente no sería programable? Pero si alguien demuestra que estoy equivocado, dame el código. . . .

Gavriel Feria
fuente
2

Para el código A, el bucle externo se ejecutará por n+1tiempos, el tiempo '1' significa el proceso que verifica si aún cumplo con el requisito. Y el ciclo interno corre ntiempos, n-2tiempos ... Por lo tanto,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²) .

Para el código B, aunque el bucle interno no intervendría y ejecutaría el foo (), el bucle interno se ejecutará n veces dependiendo del tiempo de ejecución del bucle externo, que es O (n)

Laynece
fuente
1

Me gustaría explicar el Big-O en un aspecto un poco diferente.

Big-O es solo para comparar la complejidad de los programas, lo que significa qué tan rápido crecen cuando aumentan los insumos y no el tiempo exacto que se dedica a realizar la acción.

En mi humilde opinión, en las fórmulas big-O es mejor que no uses ecuaciones más complejas (es posible que solo te quedes con las del siguiente gráfico). Sin embargo, podrías usar otra fórmula más precisa (como 3 ^ n, n ^ 3, .. .) ¡Pero más que eso puede ser a veces engañoso! Así que es mejor mantenerlo lo más simple posible.

ingrese la descripción de la imagen aquí

Me gustaría enfatizar una vez más que aquí no queremos obtener una fórmula exacta para nuestro algoritmo. Solo queremos mostrar cómo crece cuando las entradas están creciendo y compararlas con los otros algoritmos en ese sentido. De lo contrario, sería mejor utilizar diferentes métodos, como el marcado de banco.

HmT
fuente