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

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?

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²)

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.

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 ² ) - 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 ³ ) - Multiplicar dos matrices n × n por un algoritmo simple

O (c ⁿ ): 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 ⁿ ): a menudo se usa en lugar de O (n!) Para obtener fórmulas más simples para la complejidad asintótica

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 ² ), 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.

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.

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 ² /4 + n / 2) = O (n ² /4) = O (n ² )

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 ² ) <O ( N ^k ) <O (e ⁿ ) <O ( n !)

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 ₂ 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.

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.

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.

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

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!

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.

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.

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 .

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.

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.

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);

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.

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.

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.

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. . . .

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)

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.

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.