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

Question

La mayoría de las personas con un título en informática seguramente sabrán qué La O grande significa.Nos ayuda a medir qué tan (in)eficiente es realmente un algoritmo y si lo sabes en ¿En qué categoría se encuentra el problema que estás tratando de resolver? puedes descubrir si todavía es posible exprimir ese pequeño rendimiento extra.¹

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

¹ _{pero como dicen, no te excedas, La optimización prematura es la fuente de todos los males, y la optimización sin causa justificada debería merecer ese nombre también.}

Answer 1

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

---

No hay procedimiento mecanico que se puede utilizar para conseguir el BigOh.

A modo de "libro de cocina", para obtener la grandeoh 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 cálculo se ejecutan dada una entrada de cierto tamaño.

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

Por ejemplo, digamos que tienes este fragmento 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 los 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 así:

Number_Of_Steps = f(data.length)

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

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

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

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 for declaración.Recuerde que estamos contando el número de pasos computacionales, lo que significa que el cuerpo del for la declaración 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 existe una regla mecánica para contar cuántas veces el cuerpo del for se ejecuta, debe contarlo observando qué hace el código.Para simplificar los cálculos, estamos ignorando las partes de inicialización variable, condición e incremento 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. Divide los términos del polinomio y ordénalos según la tasa de crecimiento.
4. Quédate con el que crece cuando N enfoques infinity.

Nuestro 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 crece cuando f() se acerca al infinito (pensar en límites) este es el argumento de BigOh, y el sum() La función tiene un BigOh de:

O(N)

---

Hay algunos trucos para resolver algunos complicados:usar sumatorias cuando puedas.

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

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

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

El for La afirmación sobre la frase número uno es complicada.Mientras que el índice termina en 2 * N, el incremento se realiza en dos.Eso significa que la primera for solo se ejecuta N pasos, y necesitamos dividir la cuenta por dos.

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

el numero de frase dos Es aún más complicado ya que depende del valor de i.Echar un vistazo:el índice i toma los valores:0, 2, 4, 6, 8, ..., 2 * N, y el segundo for ser ejecutado:N veces el primero, N - 2 el segundo, N - 4 el tercero...hasta la etapa N/2, en la que comienza el segundo for nunca se ejecuta.

En 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, toda 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 C pasos.)

Tenemos un problema aquí:cuando i toma el valor N / 2 + 1 hacia arriba, ¡la Suma interna termina en un número negativo!Eso es imposible y está mal.Necesitamos dividir la sumatoria en dos, siendo el punto central el momento i acepta 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 asumimos una complejidad de ejecución de C constante en su cuerpo.

Ahora las sumatorias 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²)

Answer 2

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

Algunos ejemplos de cómo se usa en 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 qué tan grande sea la matriz, siempre toma el mismo tiempo constante obtener el primer elemento.

x = array[0];

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

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

Esto sería O(n) ya que como máximo tendríamos que revisar toda la lista para encontrar nuestro número.Big-O sigue siendo O(n) aunque podamos encontrar nuestro número en 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 estrecho) .

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 revisar toda la lista nuevamente para que las n se multipliquen dejándonos con n al cuadrado.

Esto es apenas un rasguño de la superficie, pero cuando se analizan algoritmos más complejos, entran en juego matemáticas complejas que involucran pruebas.Espero que esto te familiarice al menos con los conceptos básicos.

Answer 3

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

Éstos 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;usando una tabla de búsqueda de tamaño constante o una 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 ordenar;sumando dos números de n dígitos

En²) - Multiplicar dos números de n dígitos mediante un algoritmo simple;sumando dos matrices n×n;clasificación por burbujas o clasificación por inserción

En³) - Multiplicar dos matrices n×n mediante un algoritmo simple

Jefe^norte) - Encontrar la solución (exacta) al problema del viajante mediante programación dinámica;determinar si dos declaraciones lógicas son equivalentes usando fuerza bruta

O(n!) - Resolviendo el problema del viajante mediante búsqueda por fuerza bruta

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

Answer 4

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

Esto significa que entre un algoritmo en O(n) y uno en O(n²), 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 en gran medida 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.Tomemos como ejemplo la clasificación mediante clasificación rápida: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 temporales:

• El peor de los casos (normalmente el más sencillo de entender, aunque no siempre muy significativo)

• Caso promedio (generalmente mucho más difícil de entender...)

• ...

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 evil, y (si es posible) perfilando Realmente siempre debe usarse al optimizar el código.Incluso puede ayudarle a determinar la complejidad de sus algoritmos.

Answer 5

Al ver las respuestas aquí, creo que podemos concluir que la mayoría de nosotros aproximamos el orden del algoritmo por mirando hacerlo y usar el sentido común en lugar de calcularlo con, por ejemplo, el método maestro como nos pensaban en la universidad.Dicho esto, debo agregar que incluso el profesor nos animó (más adelante) a pensar sobre ello en lugar de simplemente 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 intentar determinar las características de rendimiento para el cuerpo de la función solamente en este caso, no se hace nada especial en el cuerpo, sólo una multiplicación (o la devolución del valor 1).

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

Luego intente determinar esto para el número de llamadas recursivas.En este caso tenemos n-1 llamadas recursivas.

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

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

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

---

Pedro, contestar sus problemas planteados; El método que describo aquí realmente maneja esto bastante bien.Pero tenga en cuenta que esto sigue siendo un aproximación y no una respuesta completa matemáticamente correcta.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 usó para algoritmos mucho más avanzados que el factorial que usé en este ejemplo.
Por supuesto, todo depende de qué tan bien se pueda estimar el tiempo de ejecución del cuerpo de la función y el número de llamadas recursivas, pero eso es igualmente cierto para los otros métodos.

Answer 6

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

Eso sí, esto no funciona para series infinitas.No existe una receta única para el caso general, aunque para algunos casos comunes se aplican las siguientes desigualdades:

O(registro norte) <O(norte) <O(norte registro norte) <O(norte²) <O(norte^k) < O(e^norte) <O(norte!)

Answer 7

Lo pienso en términos de información.Cualquier problema consiste en aprender una determinada 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 brindará.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 se aprende al ejecutar esa decisión.

Por ejemplo, un if Una 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.

Suponga que está buscando en 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 SI 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 quieres.Las probabilidades son 1/1024 de que lo sea y 1023/1024 de que no lo sea.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 0,01 bits.¡Has aprendido muy poco!La segunda decisión no es mucho mejor.Por eso la búsqueda lineal es tan lenta.De hecho, es exponencial en la cantidad de bits que necesitas aprender.

Supongamos que está haciendo una indexación.Suponga que la tabla está preclasificada en muchos contenedores y utiliza algunos de todos los bits de la clave para indexar directamente la entrada de la tabla.Si hay 1024 contenedores, la entropía es 1/1024 * log(1024) + 1/1024 * log(1024) + ...para 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.Por eso la búsqueda indexada es rápida.

Ahora piensa 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 clasificación requiere 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 aproximadamente igualmente probables toman aproximadamente O (N log N) pasos.Un algoritmo de clasificación O(N) es posible si se basa en una búsqueda por indexación.

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

Answer 8

Vamos a empezar desde el principio.

En primer lugar, acepte el principio de que ciertas operaciones simples con datos se pueden realizar en 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 (por ejemplo, &&).
3. Operaciones de comparación (por ejemplo, <=).
4. Operaciones de acceso a estructuras (p. ej.Indexo de la matriz como un [i], o un puntero siguiendo con el operador->).
5. Asignación simple como copiar un valor en una variable.
6. Llamadas a funciones de 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 una pequeña cantidad de instrucciones de máquina;a menudo sólo se necesitan una o dos instrucciones.Como consecuencia, varios tipos de declaraciones en C se pueden ejecutar 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 involucran llamadas a funciones en sus expresiones.
2. Leer declaraciones.
3. Escriba declaraciones que no requieran llamadas a funciones para evaluar argumentos.
4. Las declaraciones de salto rompen, continúan, gotan y return la expresión, donde la expresión no contiene una llamada de función.

En C, se forman muchos bucles para inicializando una variable de índice a algún valor e incrementando esa variable en 1 cada vez alrededor del bucle.El bucle de for-bucle 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.Se incrementa en 1 cada vez alrededor del bucle, y las iteraciones se detienen cuando alcanza n - 1.

Sin embargo, por el momento, centrémonos en la forma simple de bucle for, donde el La diferencia entre los valores final e inicial, dividida por la cantidad en la que 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 mediante una declaración de salto;en cualquier caso, es un límite superior para el número de iteraciones.

Por ejemplo, el bucle for itera ((n − 1) − 0)/1 = n − 1 times, Dado 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 bucle se detiene y no se produce iteración con i = n - 1), y 1 se agrega a Yo en cada iteración del bucle.

En el caso más simple, donde el tiempo dedicado al 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.En rigor, entonces debemos Agregue el tiempo O (1) 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 probamos una vez más de las que damos la vuelta al circuito.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 bajo que puede ser eliminado por 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) acepta 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 agregando 1.Dado que el cuerpo, la línea (2), lleva el tiempo o (1), podemos descuidar el tiempo para incrementar a 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 n y O(1), cual es O(n).

Del mismo modo, podemos unir el tiempo de ejecución del bucle exterior 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 bucle de las líneas (3) y (4) tarda O(n) 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 bucle externo toma o (n) tiempo.

La inicialización i = 0 del bucle externo y la prueba (n + 1) ST de la condición i <n también toman o (1) tiempo y se puede descuidar.Finalmente, observamos que rodeamos el bucle exterior n veces, tomando O (n) tiempo para cada iteración, dando un totalO(n^2) tiempo de ejecución.

---

Un ejemplo más práctico.

Answer 9

Si desea estimar el orden de su código empíricamente en lugar de analizarlo, puede introducir una serie de valores crecientes de n y cronometrar su código.Traza tus 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 simplemente estudiar el código.Por un lado, puedes ver si estás en el rango donde el tiempo de ejecución se acerca a su orden asintótico.Además, es posible que descubra que algún código que pensaba que era de orden O(x) es en realidad de orden O(x^2), por ejemplo, debido al tiempo dedicado a las llamadas a la biblioteca.

Answer 10

Básicamente, lo que surge el 90% de las veces es simplemente analizar bucles.¿Tiene bucles anidados simples, dobles o triples?Tienes un tiempo de ejecución O(n), O(n^2), O(n^3).

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

Answer 11

Divida el algoritmo en partes para las que conozca la notación O grande y combínelas mediante operadores O grandes.Esa es la única manera que conozco.

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

Answer 12

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

Ahora construye un árbol correspondiente a todas las matrices con las que trabajas.En la raíz tienes el array original, la raíz tiene dos hijos que son los subarreglos.Repita esto hasta que tenga matrices de un solo elemento en la parte inferior.

Dado 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 las submatrices suman n, y como tenemos O(k) por nivel, podemos sumar esto) .Solo hay niveles log(n) en el árbol ya que cada vez dividimos la entrada a la mitad.

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

Sin embargo, Big O esconde algunos detalles que en ocasiones no podemos pasar por alto.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 pueda 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) funciona dentro del bucle.

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

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

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

Answer 13

Familiaridad con los algoritmos/estructuras de datos que uso y/o análisis rápido del anidamiento de iteraciones.La dificultad es cuando llama a una función de biblioteca, posiblemente varias veces; a menudo puede no estar seguro de si está llamando a la función innecesariamente en ocasiones o qué implementación está 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 IntelliSense.

Answer 14

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

Answer 15

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

Si realmente desea responder su pregunta sobre 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 Análisis amortizado muy útil en la práctica.

Answer 16

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

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

Answer 17

Además de utilizar el método maestro (o una de sus especializaciones), pruebo mis algoritmos de forma experimental.esto no puede probar que se logre cualquier clase de complejidad particular, pero puede brindar la seguridad de que el análisis matemático es apropiado.Para ayudar con esta tranquilidad, utilizo herramientas de cobertura de código junto con mis experimentos, para asegurarme de que estoy ejercitando todos los casos.

Como ejemplo muy simple, supongamos que desea realizar una verificación de la velocidad de clasificación de la lista de .NET Framework.Podría escribir algo como lo siguiente y 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 aún más cuidado de medir simplemente 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);

Answer 18

No olvide también tener en cuenta las complejidades del espacio que también pueden ser motivo de preocupación si uno tiene recursos de memoria limitados.Entonces, por ejemplo, es posible que escuche a alguien querer 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 provenir de cuántas veces se llama algo, con qué frecuencia se ejecuta un bucle, con qué frecuencia se asigna la memoria, etc., es otra parte para responder esta pregunta.

Por último, la O grande se puede utilizar 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 el que se utiliza para describir qué tan malo puede ser un algoritmo.

Answer 19

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

El comportamiento esperado de su algoritmo es, muy simplificado, 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 concretarlo, debe poder describir la distribución de probabilidad de su "espacio de entrada" (si necesita ordenar una lista, ¿con qué frecuencia se ordenará esa lista?¿Con qué frecuencia se invierte totalmente?¿Con qué frecuencia se clasifica principalmente?) No siempre es posible que lo sepas, pero a veces sí lo sabes.

Answer 20

gran pregunta!

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

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

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, tales que 0 ≤ f(n) ≤ cg(n) para todo n ≥ k.Los valores de cyk deben ser fijos para la función f y no deben depender de n.

---

Bien, entonces, ¿qué queremos decir con complejidades del "mejor de los casos" y del "peor de los casos"?

Probablemente esto se ilustra más claramente mediante ejemplos.Por ejemplo, si utilizamos 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 requeriría tantos pasos como elementos haya en la matriz.El mejor caso sería cuando busquemos el primer elemento ya que terminaríamos después del primer control.

El punto de todos estos adjetivo-Las complejidades de los casos es que estamos buscando una manera 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 se puede argumentar que no hay un solo momento 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 ocurrió múltiple funciones para describir la complejidad de un algoritmo.Ahora, aunque buscar una matriz de tamaño n puede llevar 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 y el caso promedio. y clases en el peor de los casos.

Lo siento, esto 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 esto, será una simple cuestión de analizar su programa y buscar cosas como bucles for que dependan del tamaño de las matrices y el razonamiento basado en sus estructuras de datos, qué tipo de entrada resultaría en casos triviales y qué entrada resultaría. en el peor de los casos.

Answer 21

No sé cómo resolver esto mediante programación, pero lo primero que hace la gente es probar el algoritmo para ciertos patrones en el número 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 y se omiten los demás términos.
   
2. Si tenemos un producto de varios factores se omiten los 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 tener en cuenta la interpolación de Lagrange en el programa, que puede ser difícil de implementar.¿Y 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 demuestra que estoy equivocado, dame el código....

Answer 22

Para el código A, el bucle externo se ejecutará durante n+1 veces, el tiempo '1' significa el proceso que verifica si todavía cumplo con el requisito.Y el bucle interior corre n veces, n-2 veces....De este modo,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).

Answer 23

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 las entradas y no el tiempo exacto que se dedica a realizar la acción.

En mi humilde opinión, en las fórmulas con O grande, es mejor no usar ecuaciones más complejas (puedes limitarte a las del siguiente gráfico). Sin embargo, aún puedes usar otras fórmulas más precisas (como 3^n, n^3,... .) ¡pero más que eso a veces puede ser 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 crecen y compararlo con los otros algoritmos en ese sentido.De lo contrario, será mejor que utilice diferentes métodos, como la evaluación comparativa.