¿Qué es la notación Big O? Lo usas [duplicar]

Question

    

Esta pregunta ya tiene una respuesta aquí:

    

        
•              ¿Qué es una explicación simple en inglés de la notación “Big O”?                                      39 respuestas                          
    

    

¿Qué es la notación Big O? ¿Lo usas?

Me perdí esta clase universitaria, supongo: D

¿Alguien lo usa y da algunos ejemplos de la vida real de dónde lo usó?

---

Vea también:

¿Big-O para niños de ocho años?
Big O, ¿cómo lo calcula / aproxima?
¿Aplicó la teoría de la complejidad computacional en la vida real?

Answer 1

Una cosa importante que la mayoría de la gente olvida cuando habla de Big-O, por lo tanto, siento la necesidad de mencionar que:

No puede usar Big-O para comparar la velocidad de dos algoritmos. Big-O solo dice cuánto más lento será un algoritmo (aproximadamente) si duplica el número de elementos procesados, o cuánto más rápido será si reduce el número a la mitad.

Sin embargo, si tiene dos algoritmos completamente diferentes y uno ( A ) es O (n ^ 2) y el otro ( B ) es O (log n) , no se dice que A es más lento que B . En realidad, con 100 elementos, A podría ser diez veces más rápido que B . Solo dice que con 200 elementos, A crecerá más lento por el factor n ^ 2 y B crecerá más lentamente por el factor log n . Entonces, si compara ambos y sabe cuánto tiempo A procesa 100 elementos, y cuánto tiempo B necesita para los mismos 100 elementos, y A es más rápido que B , puede calcular a qué cantidad de elementos B superarán a A en velocidad (como la velocidad de < el código> B disminuye mucho más lentamente que el de A , superará a A tarde o temprano & # 8212; esto es seguro).

Answer 2

La notación Big O denota el factor limitante de un algoritmo. Es una expresión simplificada de cómo se escala el tiempo de ejecución de un algoritmo en relación con la entrada.

Por ejemplo (en Java):

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

Ahora piensa en lo que realmente está haciendo. Está pasando por cada carácter de entrada y agregándolos juntos. Esto parece sencillo. El problema es que La cadena es inmutable . Por lo tanto, cada vez que agregue una letra a la cadena, tendrá que crear una nueva Cadena. Para hacer esto, debe copiar los valores de la cadena antigua en la cadena nueva y agregar el nuevo carácter.

Esto significa que copiará la primera letra n veces donde n es el número de caracteres en la entrada. Copiarás el carácter n-1 veces, por lo que en total habrá copias (n-1) (n / 2) .

Esto es (n ^ 2-n) / 2 y para la notación Big O usamos solo el factor de magnitud más alto (generalmente) y eliminamos cualquier constante que se multiplique por ella y terminamos con O (n ^ 2) .

Usar algo como un StringBuilder estará en la línea de O (nLog (n)). Si calcula la cantidad de caracteres al principio y configura la capacidad del StringBuilder , puede hacer que sea O (n) .

Entonces, si tuviéramos 1000 caracteres de entrada, el primer ejemplo realizaría aproximadamente un millón de operaciones, StringBuilder realizaría 10,000 y el StringBuilder con setCapacity realizaría 1000 operaciones para hacer lo mismo. Esta es una estimación aproximada, pero la notación O (n) se trata de órdenes de magnitudes, no de tiempo de ejecución exacto.

No es algo que uso de manera regular. Sin embargo, está constantemente en mi mente cuando intento descubrir el mejor algoritmo para hacer algo.

Answer 3

Ya se ha formulado una pregunta muy similar en ¿Big-O para ocho años? . Es de esperar que las respuestas allí respondan a tu pregunta, aunque el que hizo la pregunta tenía un poco de conocimiento matemático al respecto, lo que tal vez no tengas tan claro si necesitas una explicación más completa.

Answer 4

Todos los programadores deben saber qué es la notación Big O, cómo se aplica a las acciones con estructuras de datos y algoritmos comunes (y, por lo tanto, elegir el DS y el algoritmo correctos para el problema que están resolviendo) y cómo calcularlo para su algoritmos propios.

1) Es un orden de medición de la eficiencia de un algoritmo cuando se trabaja en una estructura de datos.

2) Las acciones como 'agregar' / 'ordenar' / 'eliminar' pueden tomar diferentes cantidades de tiempo con diferentes estructuras de datos (y algoritmos), por ejemplo, 'agregar' y 'buscar' son O (1) para un hashmap , pero O (log n) para un árbol binario. La clasificación es O (nlog n) para QuickSort, pero O (n ^ 2) para BubbleSort, cuando se trata de una matriz simple.

3) Los cálculos se pueden realizar observando la profundidad del bucle de su algoritmo en general. Sin bucles, O (1), los bucles se repiten en todo el conjunto (incluso si se rompen en algún punto) O (n). ¿Si el bucle divide a la mitad el espacio de búsqueda en cada iteración? O (log n). Toma el O () más alto para una secuencia de bucles y multiplica el O () cuando anides los bucles.

Sí, es más complejo que eso. Si realmente estás interesado, consigue un libro de texto.

Answer 5

La notación

'Big-O' se usa para comparar las tasas de crecimiento de dos funciones de una variable (digamos n) a medida que n se vuelve muy grande. Si la función f crece mucho más rápido que la función g, decimos que g = O (f) implica que para n lo suficientemente grande, f siempre será mayor que g hasta un factor de escala.

Resulta que esta es una idea muy útil en informática y particularmente en el análisis de algoritmos, porque a menudo nos preocupamos con precisión por las tasas de crecimiento de las funciones que representan, por ejemplo, el tiempo que tardan dos algoritmos diferentes. De manera muy general, podemos determinar que un algoritmo con tiempo de ejecución t1 (n) es más eficiente que un algoritmo con tiempo de ejecución t2 (n) si t1 = O (t2) para n lo suficientemente grande, que normalmente es el 'tamaño' de el problema, como la longitud de la matriz o el número de nodos en el gráfico o lo que sea.

Esta estipulación, que n se hace lo suficientemente grande, nos permite hacer muchos trucos útiles. Quizás el más utilizado es que puede simplificar las funciones a sus términos de más rápido crecimiento. Por ejemplo, n ^ 2 + n = O (n ^ 2) porque a medida que n se hace lo suficientemente grande, el término n ^ 2 se vuelve mucho más grande que n que el término n es prácticamente insignificante. Así que podemos dejarlo de lado.

Sin embargo, significa que la notación de O grande es menos útil para n pequeña, porque los términos de crecimiento más lento que hemos olvidado todavía son lo suficientemente significativos como para afectar el tiempo de ejecución.

Lo que ahora tenemos es una herramienta para comparar los costos de dos algoritmos diferentes, y una abreviatura para decir que uno es más rápido o más lento que el otro. Se puede abusar de la notación Big-O, lo cual es una pena, ya que es lo suficientemente impreciso. Hay términos equivalentes para decir que una función crece menos rápido que otra, y que dos funciones crecen a la misma velocidad.

Oh, ¿y lo uso? Sí, todo el tiempo, cuando descubro qué tan eficiente es mi código, ofrece una excelente aproximación al costo de la envolvente.

Answer 6

La " Intuitición " detrás de Big-O

Imagine una "competencia" entre dos funciones sobre x, a medida que x se acerca al infinito: f (x) yg (x).

Ahora, si desde algún punto (alguna x) una función siempre tiene un valor más alto que la otra, entonces llamemos a esta función "más rápido" que el otro.

Entonces, por ejemplo, si para cada x > 100 ves que f (x) > g (x), entonces f (x) es " más rápido " que g (x).

En este caso diríamos que g (x) = O (f (x)). f (x) plantea una especie de " límite de velocidad " para g (x), ya que eventualmente lo pasa y lo deja para siempre.

Esta no es exactamente la definición de notación big-O , que también establece que f (x) solo tiene que ser más grande que C * g (x) para una C constante (que es solo otra forma de decir que no puedes ayudar a g (x) a ganar la competencia multiplicándola por un factor constante - f (x) siempre ganará al final). La definición formal también utiliza valores absolutos. Pero espero haberlo hecho intuitivo.

Answer 7

También puede valer la pena considerar que la complejidad de muchos algoritmos se basa en más de una variable, particularmente en problemas multidimensionales. Por ejemplo, recientemente tuve que escribir un algoritmo para lo siguiente. Dado un conjunto de n puntos y m polígonos, extrae todos los puntos que se encuentran en cualquiera de los polígonos. La complejidad se basa en dos variables conocidas, nym, y se desconoce cuántos puntos hay en cada polígono. La notación O grande aquí es bastante más complicada que O (f (n)) o incluso O (f (n) + g (m)). Big O es bueno cuando se trata de grandes cantidades de elementos homogéneos, pero no espere que esto sea siempre el caso.

También vale la pena señalar que el número real de iteraciones sobre los datos a menudo depende de los datos. Quicksort suele ser rápido, pero le da datos clasificados y se ralentiza. El algoritmo de mis puntos y polígonos terminó bastante rápido, cerca de O (n + (m log (m)), basado en el conocimiento previo de cómo era probable que se organizaran los datos y los tamaños relativos de n y m. Se caería mal en datos organizados al azar de diferentes tamaños relativos.

Una última cosa a considerar es que a menudo hay un intercambio directo entre la velocidad de un algoritmo y la cantidad de espacio que utiliza. La clasificación de agujeros de paloma es un buen ejemplo de esto. Volviendo a mis puntos y polígonos, digamos que todos mis polígonos fueron simples y rápidos de dibujar, y podría dibujarlos rellenos en la pantalla, por ejemplo, en azul, en una cantidad fija de tiempo cada uno. Entonces, si dibujo mis polígonos m en una pantalla negra, tomaría O (m) tiempo. Para verificar si alguno de mis n puntos estaba en un polígono, simplemente verifico si el píxel en ese punto es verde o negro. Entonces la verificación es O (n), y el análisis total es O (m + n). Lo malo, por supuesto, es que necesito un almacenamiento casi infinito si trato con coordenadas del mundo real con una precisión milimétrica ... ... zumbido.

Answer 8

También puede valer la pena considerar el tiempo amortizado , en lugar del mero caso. Esto significa, por ejemplo, que si ejecuta el algoritmo n veces, será O (1) en promedio, pero a veces puede ser peor.

Un buen ejemplo es una tabla dinámica, que es básicamente una matriz que se expande a medida que le agrega elementos. Una implementación ingenua aumentaría el tamaño de la matriz en 1 para cada elemento agregado, lo que significa que todos los elementos deben copiarse cada vez que se agregue uno nuevo. Esto daría como resultado un algoritmo O (n ² ) si estuviera concatenando una serie de matrices utilizando este método. Una alternativa es duplicar la capacidad de la matriz cada vez que necesite más almacenamiento. Aunque a veces agregar es una operación O (n) , solo tendrá que copiar los elementos O (n) por cada elemento n agregado, por lo que la operación es O (1) en promedio. Así es como se implementan StringBuilder o std :: vector .

Answer 9

¿Qué es la notación Big O?

La notación Big O es un método para expresar la relación entre muchos pasos que requerirá un algoritmo relacionado con el tamaño de los datos de entrada. Esto se conoce como la complejidad algorítmica. Por ejemplo, al ordenar una lista de tamaño N usando Bubble Sort se toman los pasos O (N ^ 2).

¿Utilizo la notación Big O?

Utilizo la notación Big O en ocasiones para transmitir complejidad algorítmica a otros programadores. Uso la teoría subyacente (por ejemplo, las técnicas de análisis de Big O) todo el tiempo cuando pienso en qué algoritmos usar.

¿Ejemplos concretos?

He utilizado la teoría del análisis de complejidad para crear algoritmos para estructuras de datos de pila eficientes que no requieren una reasignación de memoria y que admiten el tiempo promedio de O (N) para la indexación. He usado la notación Big O para explicar el algoritmo a otras personas. También he utilizado el análisis de complejidad para comprender cuándo es posible la clasificación lineal en tiempo O (N).

Answer 10

De Wikipedia .....

La notación Big O es útil cuando se analizan algoritmos para la eficiencia. Por ejemplo, el tiempo (o el número de pasos) que lleva completar un problema de tamaño n puede ser T (n) = 4n & # 178; & # 8722; 2n + 2.

A medida que n crece, n & # 178; el término llegará a dominar, de modo que todos los demás términos se pueden ignorar & # 8212; por ejemplo, cuando n = 500, el término 4n & # 178; es 1000 veces más grande que el término 2n. Ignorar lo último tendría un efecto insignificante en el valor de la expresión para la mayoría de los propósitos.

Obviamente nunca lo he usado ...

Answer 11

Debería poder evaluar la complejidad de un algoritmo. Esto, combinado con el conocimiento de cuántos elementos tomará, puede ayudarlo a determinar si no es adecuado para su tarea.

Answer 12

Dice cuántas iteraciones tiene un algoritmo en el peor de los casos.

para buscar un elemento en una lista, puede recorrer la lista hasta que obtenga el elemento. En el peor de los casos, el artículo está en el último lugar.

Digamos que hay n elementos en la lista. En el peor de los casos, toma n iteraciones. En la notación Big O es O (n).

Dice de hecho cuán eficiente es un algoritmo.