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

little big city hack 2018 (23)

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

El comportamiento esperado de su algoritmo es, muy estúpido, qué tan rápido puede esperar que su algoritmo funcione con 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 concretarlo realmente, debe poder describir la distribución de probabilidad de su "espacio de entrada" (si necesita ordenar una lista, ¿con qué frecuencia ya se va a clasificar esa lista? ¿Con qué frecuencia se invierte totalmente? a menudo, ¿es mayormente ordenado?) No siempre es posible que lo sepas, pero a veces lo haces.

La mayoría de las personas con un título en CS seguramente sabrán lo que significa Big O. Nos ayuda a medir qué tan (in) eficiente es un algoritmo y si sabe en qué categoría se encuentra el problema que está tratando de resolver , puede averiguar si todavía es posible eliminar ese pequeño rendimiento adicional. ¹

Pero tengo curiosidad, ¿cómo calculamos o aproximamos la complejidad de sus algoritmos?

¹ _{pero como dicen, no exagere,

la optimización prematura es la raíz de todo mal

, y la optimización sin una causa justificada debería merecer ese nombre también.}

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 están creciendo cuando las entradas están aumentando y no el tiempo exacto que se gasta para realizar la acción.

En mi humilde opinión, en las fórmulas de la gran O, es mejor que no utilices ecuaciones más complejas (puedes limitarte a las que aparecen en el siguiente gráfico). Sin embargo, es posible que uses otra fórmula más precisa (como 3 ^ n, n ^ 3, ... .) ¡Pero más que eso puede ser engañoso a veces! Así que mejor mantenerlo lo más simple posible.

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 comparar con los otros algoritmos en ese sentido. De lo contrario, sería mejor utilizar diferentes métodos, como el marcado de referencia.

No olvide permitir también las complejidades de espacio que también pueden ser motivo de preocupación si uno tiene recursos de memoria limitados. Entonces, por ejemplo, puedes escuchar a alguien que desea un algoritmo de espacio constante, que es básicamente una forma de decir que la cantidad de espacio que ocupa 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 esta pregunta.

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

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

Si tenemos una suma de términos, el término con la mayor tasa de crecimiento se mantiene, con otros términos omitidos.
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 debería tener en cuenta la interpolación de Lagrange en el programa, lo que puede ser difícil de implementar. ¿Y qué pasaría si el valor real 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 me demuestra que estoy equivocado, dame el código. . . .

Para el código A, el bucle externo se ejecutará por n+1 horas, el tiempo ''1'' significa el proceso que verifica si todavía cumplo con el requisito. Y el bucle interno se ejecuta n veces, n-2 veces .... 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 foo (), el bucle interno se ejecutará n veces, dependiendo del tiempo de ejecución del bucle externo, que es O (n)

gran pregunta

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

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

Visite 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 manera que 0 ≤ f (n) ≤ cg (n) para todos n ≥ k. Los valores de c y k deben fijarse para la función f y no deben depender de n.

Ok, entonces, ¿qué entendemos por complejidades de "mejor caso" y "peor caso"?

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, el peor de los casos es cuando decidimos buscar el último elemento de la matriz, ya que esto llevaría a cabo tantos pasos como elementos hay en la matriz. El mejor caso sería cuando buscamos el primer elemento, ya que habríamos terminado después de la primera comprobación.

El punto de todas estas complejidades de adjetivo- caso es que estamos buscando una manera de graficar la cantidad de tiempo que un programa hipotético se ejecuta hasta completar 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 de entrada particular. 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 creamos múltiples funciones para describir la complejidad de un algoritmo. Ahora, aunque la búsqueda de una matriz de tamaño n puede llevar varios períodos de tiempo dependiendo de lo que esté buscando en la matriz y de forma proporcional a n, podemos crear una descripción informativa del algoritmo utilizando el mejor caso, el promedio de mayúsculas y minúsculas. , y en el peor de los casos.

Lo siento, esto está tan mal escrito y carece de mucha información técnica. Pero espero 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 de los tamaños de los arreglos y el razonamiento basado en sus estructuras de datos: qué tipo de información resultaría en casos triviales y qué información resultaría en el peor de los casos.

Además de usar el método maestro (o una de sus especializaciones), pruebo mis algoritmos de manera experimental. Esto no puede probar que se haya logrado ninguna clase de complejidad particular, pero puede proporcionar la seguridad de que el análisis matemático es apropiado. Para ayudar con esta confirmación, utilizo las herramientas de cobertura de código junto con mis experimentos, para asegurarme de que estoy ejercitando todos los casos.

Como un ejemplo muy simple, diga que desea realizar una comprobación de la velocidad en la velocidad de clasificación de la estructura de .NET. Podría 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 tener mucho más cuidado de medir el algoritmo y no incluir 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);

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

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

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

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

el cual 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).

A continuación, intente y determine esto para el número de llamadas recursivas . En este caso tenemos n-1 llamadas recursivas.

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

Luego ponga esos dos juntos 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í realmente maneja esto bastante bien. Pero tenga en cuenta que esto sigue siendo una aproximación y no una respuesta matemáticamente correcta. El método descrito aquí también es uno de los métodos que aprendimos en la universidad, y si recuerdo correctamente se usó para algoritmos mucho más avanzados que el factorial que usé 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.

Básicamente, lo que surge el 90% del tiempo es simplemente analizar los bucles. ¿Tienes bucles anidados simples, dobles, triples? Tienes el tiempo de ejecución 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 sea más difícil que solo mirar sus bucles (para las declaraciones, mientras que, goto, etc ...)

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

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

Digamos que tenemos una serie 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 el tamaño de 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. El Big-O sigue siendo O (n) aunque podríamos encontrar nuestro número en el primer intento y ejecutar el bucle una vez, porque Big-O describe el límite superior para un algoritmo (omega es para límite inferior y theta es para límite firme) .

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 paso del bucle externo (O (n)) tenemos que repasar la lista completa de nuevo para que las n se multipliquen dejándonos con n al cuadrado.

Esto apenas roza la superficie, pero cuando se analizan algoritmos más complejos, entran en juego complejos cálculos matemáticos con pruebas. Espero que esto te familiarice con lo básico al menos, sin embargo.

Creo que es menos útil en general, pero en aras de la integridad, 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.

Divida el algoritmo en partes para las que sabe la gran notación O, y combínelas a través de operadores O grandes. Esa es la única manera que conozco.

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

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 multiplicar los conteos de bucles para bucles anidados), especialmente. cuando todo lo que quieres es una estimación de límite superior, y no te importa si es demasiado pesimista, que creo que es probablemente de lo que trata tu 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 caso", he encontrado que el análisis amortizado es muy útil en la práctica.

Familiaridad con los algoritmos / estructuras de datos que utilizo y / o análisis de vista rápida de anidación de iteración. La dificultad radica en que cuando llama a una función de biblioteca, posiblemente varias veces, a menudo puede estar inseguro de si está llamando a la función innecesariamente a veces o qué implementación está utilizando. Tal vez las funciones de la biblioteca deban 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 .

Haré todo lo posible para explicarlo aquí en términos sencillos, pero tenga en cuenta que este tema requiere un par de meses para que mis alumnos lo comprendan. Puede encontrar más información en el capítulo 2 del libro Estructuras de datos y algoritmos en Java .

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

Como un "libro de cocina", para obtener el BigOh 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 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, 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 de la matriz, y queremos crear una fórmula para contar la 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 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 N toma el valor data.length . 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 punto en adelante, vamos a suponer que cada oración que no dependa del tamaño de los datos de entrada lleva un número computacional constante de pasos.

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 matriz de data .

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 instrucción for . Recuerde que estamos contando el número de pasos computacionales, lo que significa que el cuerpo de la instrucción for se ejecuta N veces. Eso es lo mismo que agregar C , N veces:

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

No hay una regla mecánica para contar la cantidad de veces que se ejecuta el cuerpo de for , debe contarlo observando qué hace el código. Para simplificar los cálculos, ignoramos las partes de inicialización, condición e incremento de variables de la instrucción for .

Para obtener el BigOh real necesitamos el análisis asintótico de la función. Esto se hace aproximadamente de esta manera:

Quita todas las constantes C .
Desde f() obtener el polynomium en su standard form .
Divida los términos del polinomio y ordénelos por la tasa de crecimiento.
Mantén el que crece más grande cuando N acerca al infinity .

Nuestro f() tiene dos términos:

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

Quitando todas las constantes C y partes redundantes:

f(N) = 1 + N ^ 1

Dado que el último término es el que crece cuando f() acerca al infinito (piensa en los limits ), este es el argumento de BigOh, y la función sum() tiene un BigOh de:

O(N)

Hay algunos trucos para resolver algunos complicados: usa summations siempre que puedas.

Como ejemplo, este código puede resolverse fácilmente mediante sumas:

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() . Mientras que lo habitual es ser O(1) , debe preguntar a sus profesores al respecto. O(1) significa (casi, en su mayoría) constante C , independientemente del tamaño N

La declaración de la oración número uno es complicada. Mientras que el índice termina en 2 * N , el incremento se realiza en dos. Eso significa que el primero for se ejecuta solo N pasos, 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 for ejecutarse: N veces el primero, N - 2 el segundo, N - 4 la tercera ... hasta la etapa N / 2, en la que nunca se ejecuta la segunda for .

En la fórmula, eso significa:

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

Una vez más, estamos contando el número de pasos . Y, por definición, cada resumen 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 ) )

(Suponemos que foo() es O(1) y toma los pasos de C ).

Tenemos un problema aquí: cuando tomo el valor N / 2 + 1 hacia arriba, ¡la Suma interna termina en un número negativo! Eso es imposible e incorrecto. Necesitamos dividir la suma en dos, siendo el punto central el momento en que tomo 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 fundamental i > N / 2 , el interior for no se ejecutará, y estamos asumiendo una complejidad de ejecución de C constante en su cuerpo.

Ahora las sumas se pueden simplificar usando algunas reglas de identidad:

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

Aplicando un poco 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²)

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 manera de resolver la complejidad de los algoritmos de dividir y conquistar es el método de árbol. Digamos que tiene una versión de quicksort con el procedimiento de la mediana, por lo que divide la matriz en subarreglos perfectamente equilibrados 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 los subarrays. Repita esto hasta que tenga matrices de elementos individuales en la parte inferior.

Ya que podemos encontrar la mediana en tiempo O (n) y dividir la matriz en dos partes en 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) la matriz completa, por lo que el trabajo por nivel es O (n) (los tamaños de los subarrays se suman a n, y como tenemos O (k) por nivel, podemos sumar esto) . Solo hay niveles de registro (n) en el árbol, ya que cada vez que dividimos la entrada a la mitad.

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

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

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

y asumamos 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 inmutarse. El razonamiento es que tiene n iteraciones en el bucle for y O (1) trabaja en el lado del bucle.

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

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

¡Así que este algoritmo se ejecuta en tiempo cuadrada!

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 por el registro ₂ de la probabilidad inversa de esa rama. Eso es lo que aprendes ejecutando esa decisión.

Por ejemplo, una instrucción if 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.

Supongamos que está buscando una tabla de N elementos, como N = 1024. Eso 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ás haciendo una búsqueda lineal. Miras el primer elemento y preguntas si es el que quieres. Las probabilidades son 1/1024 de lo que es, y 1023/1024 que no lo 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. Supongamos que la tabla está pre-ordenada en un montón de bandejas, y utiliza algunos de los bits de 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 elementos, 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 clasificación lleva aproximadamente N veces el número de pasos de la búsqueda subyacente.

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

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

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

Para el segundo bucle, i está comprendido entre 0 y n incluido para el bucle externo; entonces el bucle interno se ejecuta cuando j es estrictamente mayor que n , lo cual es imposible.

Pequeño recordatorio: la notación big O se utiliza para denotar 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 ² ), 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. La clasificación se realiza utilizando 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 (normalmente mucho más difícil de averiguar ...)
...

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

Como usted dice, premature optimisation is the root of all evil , y (si es posible) el perfil siempre debería usarse cuando se optimiza el código. Incluso puede ayudarlo a determinar la complejidad de sus algoritmos.

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

Estos son algunos de los casos más comunes, recogidos 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 tabla hash

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

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

O (n ² ) - Multiplicando dos números de n dígitos por un algoritmo simple; añadiendo dos matrices n × n; tipo de burbuja o tipo de inserción

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

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

O (n!) - Resolver el problema del vendedor ambulante mediante la búsqueda de fuerza bruta

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

Si desea estimar el orden de su código de forma empírica en lugar de analizarlo, puede mantener una serie de valores crecientes de n y el tiempo de su código. Traza tus tiempos en una escala de registro. 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, puedes ver si estás en el rango donde el tiempo de ejecución se aproxima 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 empleado en las llamadas a la biblioteca.

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

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

Esto no funciona para series infinitas, fíjate. 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 ² ) <O ( N ^k ) <O (e ⁿ ) <O ( n !)

Vamos a empezar desde el principio.

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

Operaciones aritméticas (ej. + O%).
Operaciones lógicas (ej., &&).
Operaciones de comparación (por ejemplo, <=).
Operaciones de acceso a la estructura (por ejemplo, indexación de matrices como A [i], o puntero que sigue con el operador ->).
Asignación simple como copiar un valor en una variable.
Llamadas a funciones de la biblioteca (por ejemplo, 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 realizar con un pequeño número de instrucciones de la máquina; a menudo solo se necesitan una o dos instrucciones Como consecuencia, varios tipos de declaraciones en C pueden ejecutarse en tiempo O(1) , es decir, en una cantidad constante de tiempo independiente de la entrada. Estos simples incluyen

Sentencias de asignación que no involucran llamadas a funciones en sus expresiones.
Lea las declaraciones.
Escriba declaraciones que no requieran llamadas a funciones para evaluar argumentos.
Las declaraciones de salto rompen, continúan, van y devuelven expresión, donde expresión no contiene una llamada de función.

En C, muchos bucles for se forman al inicializar una variable de índice a algún valor e incrementando esa variable en 1 cada vez que rodea el bucle. El for-loop finaliza cuando el índice alcanza algún límite. Por ejemplo, el for-loop

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 que gira alrededor del bucle, y las iteraciones se detienen cuando alcanza n - 1.

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

Por ejemplo, el bucle 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 i alcanza n − 1, el bucle se detiene y no se produce 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 empleado en el cuerpo del bucle es el mismo para cada iteración, podemos multiplicar el límite superior grande-oh para el cuerpo por el número de veces alrededor del bucle . En sentido estricto, debemos agregar O (1) tiempo para inicializar el índice de bucle y O (1) para la primera comparación del índice de bucle con el límite , porque probamos una vez más de lo que hacemos en el bucle. Sin embargo, a menos que sea posible ejecutar el bucle cero veces, el tiempo para inicializar el bucle y probar el límite una vez es un término de orden inferior que puede ser descartado por la regla de la suma.

Ahora considera 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, vamos alrededor del bucle n veces, como podemos determinar restando el límite inferior del límite superior encontrado en la línea (1) y luego agregando 1. Ya que el cuerpo, línea (2), toma O (1) tiempo, podemos descuidar el tiempo para incrementar j y el tiempo para comparar j con n, ambos también son O (1). Por lo tanto, el tiempo de ejecución de las líneas (1) y (2) es el producto de n y O (1) , que es O(n) .

Del mismo modo, podemos limitar el tiempo de ejecución del bucle externo que consta de 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 bucle de líneas (3) y (4) lleva 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 (n + 1) prueba de la condición i <n también toman el tiempo O (1) y pueden descuidarse. Finalmente, observamos que vamos alrededor del bucle externo n veces, tomando O (n) tiempo para cada iteración, dando un tiempo total de O(n^2) ejecución.

Un ejemplo más práctico.