Pregunta Gran O, ¿cómo se calcula / se aproxima?


La mayoría de las personas con un título en CS ciertamente sabrá qué Big O significa. Nos ayuda a medir cómo (en) realmente es un algoritmo eficiente y si usted conoce de qué categoría se establece el problema que está tratando de resolver puede averiguar si todavía es posible exprimir ese pequeño rendimiento extra.1

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

1  pero como dicen, no exageres, La optimización temprana es la raíz de todo maly la optimización sin una causa justificada también debería merecer ese nombre.


784
2017-08-06 10:18


origen


Respuestas:


Soy asistente de profesor en mi universidad local en el curso de Estructuras de Datos y Algoritmos. Haré todo lo posible para explicarlo aquí en términos simples, pero se advirtió que este tema les toma a mis alumnos un par de meses para finalmente captarlo. Puede encontrar más información sobre el Capítulo 2 de la Estructuras de datos y algoritmos en Java libro.


No hay procedimiento mecánico que se puede usar para obtener BigOh.

Como un "libro de cocina", para obtener el BigOh 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 dado 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 es el número de pasos, más rápido es el algoritmo.

Por ejemplo, digamos que tienes 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 el complejidad computacional de esa función:

Number_Of_Steps = f(N)

Entonces tenemos f(N), una función para contar la cantidad 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 data.length valor. 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 se numera de 1 a 4.

Hay muchas formas de calcular BigOh. De ahora en adelante, vamos a suponer que cada oración que no depende del tamaño de los datos de entrada toma una constante C numera los pasos computacionales.

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

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

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

La siguiente parte es definir el valor de la for declaración. Recuerde que estamos contando el número de pasos computacionales, lo que significa que el cuerpo del for declaración se ejecuta N veces. Eso es lo mismo que agregar C, Nveces:

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

No hay una regla mecánica para contar cuántas veces el cuerpo del for se ejecuta, necesitas contarlo mirando qué hace el código. Para simplificar los cálculos, estamos ignorando la inicialización variable, la condición y el incremento de las partes del for declaració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() consigue 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 crece más grande cuando N enfoques infinity.

Nuestra f() tiene dos términos:

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

Quitando todo el C constantes y partes redundantes:

f(N) = 1 + N ^ 1

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

O(N)

Hay algunos trucos para resolver algunos trucos: usar Sumaciones cuando puedas.

Como ejemplo, este código se puede resolver fácilmente usando sumas:

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

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

los for La declaración en la oración número uno es engañosa. Mientras el índice termina en 2 * N, el incremento se realiza por dos. Eso significa que el primero for solo se ejecuta N pasos, y tenemos que dividir el conteo por dos.

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

El número de la oración dos es aún más complicado 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 Ejecutar: N veces el primero, N - 2 el segundo, N - 4 el tercero ... hasta el N / 2 etapa, en el que el segundo for nunca se ejecuta.

En la fórmula, eso significa:

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

De nuevo, estamos contando la cantidad de pasos. Y, por definición, cada resumen debe comenzar siempre en uno, y terminar en un número mayor o igual a uno.

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

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

Tenemos un problema aquí: cuando i toma el valor N / 2 + 1 hacia arriba, ¡la Suma interna termina en un número negativo! Eso es imposible y equivocado. Necesitamos dividir la suma en dos, siendo el punto fundamental el momento i toma N / 2 + 1.

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

Desde el momento crucial i > N / 2, el interior for no 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. Sumatoria (w de 1 a N) (C) = N * C
  2. Sumatoria (w de 1 a N) (A (+/-) B) = Sumatoria (w de 1 a N) (A) (+/-) Sumatoria (w de 1 a N) (B)
  3. Sumatoria (w de 1 a N) (w * C) = C * Sumatoria (w de 1 a N) (w) (C es una constante, independiente de w)
  4. Sumatoria (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²)

1390
2018-01-31 15:33



Big O da 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 usar en cualquier otro lugar.

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, esto 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. El Big-O sigue siendo O (n) aunque podríamos encontrar nuestro número al primer intento y ejecutarlo 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 apretado) .

Cuando llegamos a los bucles anidados:

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

Esto es O (n ^ 2) ya que para cada pasada del ciclo externo (O (n)) tenemos que repasar toda la lista nuevamente para que las n se multipliquen dejándonos con n al cuadrado.

Esto apenas araña la superficie, pero cuando se analizan algoritmos más complejos, entran en juego complejas matemáticas que incluyen pruebas. Espero que esto te familiarice con lo básico al menos sin embargo.


190
2017-08-06 13:34



Aunque 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, levantados de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O (1) - Determinando 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 artículo en una lista desordenada; agregando dos números de n dígitos

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

En3) - Multiplicar dos matrices n × n por algoritmo simple

Jefenorte) - Encontrar la solución (exacta) al problema del vendedor ambulante usando programación dinámica; determinar si dos declaraciones lógicas son equivalentes usando la fuerza bruta

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

Ennorte) - Usado a menudo en lugar de O (n!) Para derivar fórmulas más simples para la complejidad asintótica


87
2017-09-05 19:09



Pequeño recordatorio: el big O la notación se usa para denotar asintótico complejidad (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 (n2), el más rápido no es siempre 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 ordenación usando la ordenació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:

  • Peor caso (generalmente el más simple de entender, aunque no siempre muy significativo)
  • Caso promedio (generalmente mucho más difícil de descubrir ...)

  • ...

Una buena introducción es Una 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) perfil realmente siempre se debe utilizar al optimizar el código. Incluso puede ayudarte a determinar la complejidad de tus algoritmos.


40
2017-08-23 20:43



Al ver las respuestas aquí, creo que podemos concluir que la mayoría de nosotros sí aproximamos el orden del algoritmo mirando y usar el sentido común en lugar de calcularlo con, por ejemplo, el método maestro como nos pensaron en la universidad. Dicho esto, debo agregar que incluso el profesor nos animó (más adelante) a pensar al respecto 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 recursivamente calcula el factorial del número dado.

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

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

Luego intente y determine esto para el cantidad de llamadas recursivas. En este caso, tenemos n-1 llamadas recursivas.

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

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

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


Peter, contestar sus problemas planteados; el método que describo aquí en realidad maneja esto bastante bien. Pero ten en cuenta que esto sigue siendo un aproximación y no una respuesta matemáticamente correcta completa. El método descrito aquí también es uno de los métodos que se nos enseñó en la universidad, y si no recuerdo mal se utilizó para algoritmos mucho más avanzados que el factorial que utilicé en este ejemplo.
Por supuesto, todo depende de qué tan bien se puede 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.


26
2017-08-07 08:10



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

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 (registro norte) <O (norte) <O (norte Iniciar sesión norte) <O (norte2) <O (nortek) <O (enorte) <O (norte!


25
2018-01-31 13:30



Lo pienso en términos de información. Cualquier problema consiste en aprender una cierta cantidad 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 registro2 de la probabilidad inversa de esa rama. Eso es cuánto aprendes al ejecutar esa decisión.

Por ejemplo, un if declaració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 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 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 = alrededor de .01 bit. ¡Has aprendido muy poco! La segunda decisión no es mucho mejor. Es por eso que la búsqueda lineal es muy lenta. De hecho, es exponencial en la cantidad de bits que necesita aprender.

Supongamos que está haciendo indexación. Supongamos que la tabla está previamente clasificada 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 los 1024 posibles resultados. 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 piense en clasificar. 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 ordenación lleva aproximadamente N veces el número de pasos de la búsqueda subyacente.

Por lo tanto, los géneros basados ​​en decisiones binarias que tienen resultados aproximadamente igualmente probables toman todos los pasos de O (N log N). Un algoritmo de ordenación O (N) es posible si está basado en la búsqueda de indexación.

Descubrí que casi todos los problemas de rendimiento algorítmico se pueden analizar de esta manera.


19
2018-03-10 13:24



Vamos a empezar desde el principio.

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

  1. Operaciones aritméticas (por ejemplo, + o%).
  2. Operaciones lógicas (por ejemplo, &&).
  3. Operaciones de comparación (p. Ej., <=).
  4. Operaciones de acceso a la estructura (por ejemplo, indexación de matrices como A [i], o seguimientos de punteros lowing con el operador ->).
  5. Asignación simple como copiar un valor en una variable.
  6. 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 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 en 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 de función en sus expresiones.
  2. Leer declaraciones
  3. Escribir declaraciones que no requieren llamadas a funciones para evaluar argumentos.
  4. Las instrucciones de salto rompen, continúan, regresan y devuelven expresiones, donde expresión no contiene una llamada de función.

En C, muchos for-loops se forman inicializando una variable de índice a algún valor y incrementando esa variable en 1 cada vez alrededor del bucle. El for-loop finaliza cuando el índice alcanza un 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;
}

usa la variable de índice i. Incrementa i por 1 cada vez que pasa el ciclo, y las iteraciones parar 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 en que se incrementa la variable índice, nos dice cuántas veces vamos por el ciclo. Ese conteo es exacto, a menos que haya formas de salir del bucle 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 for-loop 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 alcanza n-1, el ciclo se detiene y no se produce iteración con i = n-1), y se agrega 1 a i en cada iteración del ciclo.

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 circuito. Estrictamente hablando, debemos entonces agregue O (1) tiempo para inicializar el índice de bucle y el tiempo O (1) para la primera comparación del índice de bucle con el límite, porque lo probamos una vez más que salimos del ciclo. Sin embargo, a menos es 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 bajo que puede eliminarse mediante la regla de suma.


Ahora considere este ejemplo:

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

Lo sabemos línea 1) toma O(1) hora. Claramente, damos la vuelta al ciclo n veces, como podemos determinar restando el límite inferior del límite superior encontrado en línea (1) y luego agregue 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, que 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), cual es O(n).

Del mismo modo, podemos vincular el tiempo de ejecución del bucle externo que consiste en 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 O (n) el tiempo. 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 ciclo externo toma O (n) tiempo.

La inicialización i = 0 del bucle externo y la (st + n) prueba de la condición Igualmente tomo O (1) tiempo y puedo ser descuidado. Finalmente, observamos que vamos alrededor del bucle externo n veces, tomando O (n) el tiempo para cada iteración, dando un total O(n^2) tiempo de ejecución.


Un ejemplo más práctico.

enter image description here


17
2018-02-02 15:30



Si desea estimar el orden de su código empíricamente en lugar de analizar el código, puede incluir una serie de valores crecientes de ny de tiempo de su código. Trace sus 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, puede ver si se encuentra en el rango donde el tiempo de ejecución se acerca a su orden asintótica. 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 que pasó en las llamadas a la biblioteca.


11
2017-12-11 20:49