optimization - relativamente - notacion big o en java
¿Qué es la notación Big O? ¿Lo usas? (12)
¿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 un algoritmo requerirá en relación 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ños N usando Bubble Sort toma O (N ^ 2) pasos.
¿Uso la notación Big O?
Utilizo la notación Big O ocasionalmente para transmitir complejidad algorítmica a otros programadores. Utilizo 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 el análisis de la teoría de la complejidad para crear algoritmos para estructuras de datos de pila eficientes que no requieren reasignación de memoria y que admiten un tiempo promedio de O (N) para la indexación. He utilizado la notación Big O para explicar el algoritmo a otras personas. También utilicé el análisis de complejidad para comprender cuándo es posible la ordenación del tiempo lineal O (N).
Esta pregunta ya tiene una respuesta aquí:
¿Qué es la notación Big O? ¿Lo usas?
Extrañaba esta clase de la universidad, supongo: D
¿Alguien lo usa y da algunos ejemplos de la vida real de dónde lo usaron?
Ver también:
Big-O para Ocho años de edad?
Gran O, ¿cómo se calcula / se aproxima?
¿Aplicaste la teoría de la complejidad computacional en la vida real?
De Wikipedia .....
La notación Big O es útil cuando se analizan algoritmos para la eficiencia. Por ejemplo, el tiempo (o la cantidad de pasos) necesarios para completar un problema de tamaño n podría ser T (n) = 4n² - 2n + 2.
A medida que n crece, el término n² dominará, de modo que todos los otros términos pueden despreciarse; por ejemplo, cuando n = 500, el término 4n² es 1000 veces más grande que el término 2n. Ignorar esto ú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 ...
Debería poder evaluar la complejidad de un algoritmo. Esto combinado con un conocimiento de cuántos elementos tomará puede ayudarlo a determinar si no es adecuado para su tarea.
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 artículo. 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 de Big O es O (n).
Dice objetivamente cuán eficiente es un algoritmo.
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 hace 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 si n es 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 precisamente por las tasas de crecimiento de funciones que representan, por ejemplo, el tiempo empleado por dos algoritmos diferentes. Muy groseramente, 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 la cantidad de nodos en el gráfico o lo que sea.
Esta estipulación, que se vuelve lo suficientemente grande, nos permite obtener muchos trucos útiles. Quizás el más utilizado es que puede simplificar las funciones hasta sus términos de crecimiento más rápido. Por ejemplo, n ^ 2 + n = O (n ^ 2) porque como n es lo suficientemente grande, el término n ^ 2 es mucho más grande que n que el término n es prácticamente insignificante. Entonces podemos dejarlo de consideración.
Sin embargo, sí 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. La notación de Big-O puede ser abusada, ¡lo cual es una pena ya que ya es bastante impreciso! Hay términos equivalentes para decir que una función crece menos rápidamente que otra, y que las dos funciones crecen a la misma velocidad.
Oh, ¿y lo uso? Sí, todo el tiempo, cuando estoy averiguando qué tan eficiente es mi código, ofrece una excelente aproximación al costo.
La notación Big O denota el factor limitante de un algoritmo. Es una expresión simplificada de cómo el tiempo de ejecución de un algoritmo escala con relación a 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 esto está haciendo en realidad. Está revisando todos los caracteres de entrada y los está agregando. Esto parece sencillo. El problema es que String es inmutable . Entonces, cada vez que agregue una letra a la cadena, debe crear una nueva Cadena. Para hacer esto, debe copiar los valores de la cadena anterior en la nueva cadena y agregar el nuevo carácter.
Esto significa que va a copiar la primera letra n veces donde n es el número de caracteres en la entrada. Copiará el carácter n-1 veces, por lo que en total habrá (n-1)(n/2) copias.
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 las constantes que se multiplican por él y terminamos con O(n^2) .
Usar algo como un StringBuilder será a lo largo de las líneas de O (nLog (n)). Si calcula la cantidad de caracteres al principio y establece la capacidad de StringBuilder , puede obtener 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 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 magnitud, no de tiempo de ejecución exacto.
No es algo que uso por ejemplo regularmente. Sin embargo, constantemente me viene a la mente cuando trato de encontrar el mejor algoritmo para hacer algo.
También puede valer la pena considerar el tiempo amortizado , en lugar de solo el peor de los casos. 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 básicamente es una matriz que se expande a medida que le agregas elementos. Una implementación ingenua aumentaría el tamaño de la matriz en 1 por cada elemento agregado, lo que significa que todos los elementos deben copiarse cada vez que se agrega uno nuevo. Esto daría como resultado un algoritmo O (n 2 ) si concatenas una serie de matrices con este método. Una alternativa es duplicar la capacidad de la matriz cada vez que necesite más almacenamiento. Aunque agregar es una operación O (n) a veces, solo necesitará copiar O (n) elementos para cada n elementos agregados, por lo que la operación es O (1) en promedio. Así es como se implementan cosas como StringBuilder o std :: vector .
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, ym 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 la cantidad desconocida de cuántos puntos hay en cada polígono. La notación O grande aquí es un poco 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 artículos homogéneos, pero no esperes que este 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 es generalmente rápido, pero le da datos preestablecidos y se ralentiza. Mis puntos y polígonos alogorithm terminaron 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. Caería mal en datos aleatoriamente organizados de diferentes tamaños relativos.
Una última cosa a considerar es que a menudo existe un intercambio directo entre la velocidad de un algoritmo y la cantidad de espacio que utiliza. La clasificación de agujeros de palomas 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 pude dibujarlos llenos en la pantalla, decir en azul, en un tiempo fijo cada uno. Entonces, si dibujo mis m polígonos en una pantalla negra, tomaría O (m). 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 el cheque es O (n), y el análisis total es O (m + n). La desventaja, por supuesto, es que necesito un almacenamiento casi infinito si estoy tratando con las coordenadas del mundo real con precisión milimétrica ... ... ho hum.
Todo programador debe estar al tanto de lo que es la notación Big O, cómo se aplica a las acciones con estructuras de datos y algoritmos comunes (y así elegir el DS correcto y el algoritmo para el problema que están resolviendo) y cómo calcularlo para sus propios algoritmos.
1) Es un orden de medida de la eficacia de un algoritmo cuando se trabaja en una estructura de datos.
2) 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. Sort 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 hacer observando la profundidad de bucle de su algoritmo en general. No hay bucles, O (1), bucles que iteran sobre todo el conjunto (incluso si se rompen en algún punto) O (n). Si el bucle reduce a la mitad el espacio de búsqueda en cada iteración? O (log n). Tome la O () más alta para una secuencia de bucles, y multiplique la O () cuando anide bucles.
Sí, es más complejo que eso. Si realmente te interesa, obtén un libro de texto.
Una cosa importante que la mayoría de la gente olvida al hablar de Big-O, por lo tanto, siento la necesidad de mencionar eso:
No puede usar Big-O para comparar la velocidad de dos algoritmos. Big-O solo dice cuánto tardará un algoritmo (aproximadamente) si duplica la cantidad de elementos procesados, o cuánto más rápido obtendrá 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 lentamente con el factor n^2 y B crecerá más lentamente con el factor log n . Por lo tanto, si compara ambos y sabe cuánto tiempo tarda A para procesar 100 elementos, y cuánto tiempo B necesita para los mismos 100 artículos, y A es más rápido que B , puede calcular a qué cantidad de elementos B superará A en velocidad (ya que la velocidad de B disminuye mucho más lentamente que la de A , superará a A tarde o temprano, esto es seguro).
Ya se ha hecho una pregunta muy similar en Big-O para Ocho años de edad? . Afortunadamente, las respuestas allí responderán a su pregunta, aunque la persona que hizo la pregunta allí tenía un poco de conocimiento matemático sobre todo lo cual no puede aclarar si necesita una explicación más completa.
La "intuición" detrás de Big-O
Imagine una "competencia" entre dos funciones sobre x, cuando x se acerca al infinito: f (x) yg (x).
Ahora, si desde algún punto encendido (alguna x) una función siempre tiene un valor más alto que el otro, entonces llamemos a esta función "más rápido" que la otra.
Entonces, por ejemplo, si por 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 g (x) = O (f (x)). f (x) presenta 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 de O grande , que también establece que f (x) solo tiene que ser mayor que C * g (x) para alguna C constante (que es solo otra forma de decir que no se puede ayuda 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 usa valores absolutos. Pero espero haber logrado que sea intuitivo.