rapper examples complexity big algorithm theory big-o metrics

algorithm - examples - Big-O para ocho años de edad?



big o notation sorting (25)

Esta pregunta ya tiene una respuesta aquí:

Estoy preguntando más sobre lo que esto significa para mi código. Entiendo matemáticamente los conceptos, solo me cuesta trabajo entender lo que significan conceptualmente. Por ejemplo, si uno fuera a realizar una operación O (1) en una estructura de datos, entiendo que la cantidad de operaciones que debe realizar no aumentará porque hay más elementos. Y una operación O (n) significaría que realizaría un conjunto de operaciones en cada elemento. ¿Alguien podría llenar los espacios en blanco aquí?

  • ¿Cómo exactamente lo que haría una operación O (n ^ 2)?
  • ¿Y qué diablos significa si una operación es O (n log (n))?
  • ¿Y alguien tiene que fumar crack para escribir una O (x!)?

¿Recuerdas la fábula de la tortuga y la liebre (tortuga y conejo)?

A largo plazo, la tortuga gana, pero a corto plazo la liebre gana.

Eso es como O (logN) (tortuga) contra O (N) (liebre).

Si dos métodos difieren en su gran O, entonces hay un nivel de N en el que uno de ellos ganará, pero el gran O no dice nada acerca de cuán grande es ese N.

Dígale a su registro de ocho años (n) significa la cantidad de veces que tiene que cortar una longitud y un registro en dos para que alcance el tamaño n = 1: p

O (n log n) generalmente está ordenando O (n ^ 2) usualmente está comparando todos los pares de elementos

Esto podría ser demasiado matemático, pero aquí está mi intento. ( Soy matemático.)

Si algo es O ( f ( n )), entonces el tiempo de ejecución en n elementos será igual a A f ( n ) + B (medido en, digamos, ciclos de reloj u operaciones de la CPU). Es clave para comprender que también tiene estas constantes A y B , que surgen de la implementación específica. B representa esencialmente la "sobrecarga constante" de su operación, por ejemplo, un preprocesamiento que usted realiza no depende del tamaño de la colección. A representa la velocidad de su algoritmo real de procesamiento de elementos.

La clave, sin embargo, es que usas la notación O grande para descubrir qué tan bien se escalará algo . Entonces, esas constantes realmente no importarán: si está tratando de averiguar cómo escalar de 10 a 10000 elementos, ¿a quién le importa la sobrecarga constante B ? Del mismo modo, otras preocupaciones (ver más abajo) sin duda superarán el peso de la constante multiplicativa A.

Así que el trato real es f ( n ). Si f no crece en absoluto con n , por ejemplo, f ( n ) = 1, tendrá una escala fantástica: su tiempo de ejecución siempre será A + B. Si f crece linealmente con n , es decir, f ( n ) = n , su tiempo de ejecución se escalará de la mejor manera posible, si sus usuarios esperan 10 ns por 10 elementos, esperarán 10000 ns por 10000 Elementos (ignorando la constante aditiva). Pero si crece más rápido, como n 2 , entonces estás en problemas; las cosas comenzarán a desacelerarse demasiado cuando tengas colecciones más grandes. f ( n ) = n log ( n ) es un buen compromiso, generalmente: su operación no puede ser tan simple como para dar una escala lineal, pero ha logrado reducir las cosas de tal manera que se escale mucho mejor que f ( n ) = n 2 .

En la práctica, aquí hay algunos buenos ejemplos:

  • O (1): recuperar un elemento de una matriz. Sabemos exactamente dónde está en la memoria, así que solo vamos a buscarlo. No importa si la colección tiene 10 artículos o 10000; todavía está en el índice (por ejemplo) 3, por lo que simplemente saltamos a la ubicación 3 en la memoria.
  • O ( n ): recuperar un elemento de una lista vinculada. Aquí, A = 0.5, porque en promedio tendrás que recorrer la mitad de la lista vinculada antes de encontrar el elemento que estás buscando.
  • O ( n 2 ): varios algoritmos de clasificación "tontos". Debido a que generalmente su estrategia involucra, para cada elemento ( n ), miras a todos los otros elementos (por lo tanto, otra n , que da n 2 ), luego te colocas en el lugar correcto.
  • O ( n log ( n )): varios algoritmos de clasificación "inteligentes". Resulta que solo necesita ver, por ejemplo, 10 elementos en una colección de 10 10 elementos para clasificarse inteligentemente en relación con todos los demás miembros de la colección. Debido a que todos los demás también verán 10 elementos, y el comportamiento emergente está orquestado de manera correcta para que esto sea suficiente para producir una lista ordenada.
  • O ( n !): Un algoritmo que "intenta todo", ya que hay (proporcional a) n ! posibles combinaciones de n elementos que podrían resolver un problema dado. Así que simplemente recorre todas esas combinaciones, las prueba y luego se detiene cuando tiene éxito.

Intentaré realmente escribir una explicación para un niño de ocho años real, aparte de los términos técnicos y las nociones matemáticas.

¿Cómo exactamente lo que haría una operación O(n^2) ?

Si estás en una fiesta, y hay n personas en la fiesta incluyéndote a ti. Cuántos apretones de manos se necesitan para que todos hayan temblado a todos los demás, dado que la gente probablemente olvidará a quién tacharon en algún momento

Nota: esto se aproxima a un rendimiento simple n(n-1)que está lo suficientemente cerca n^2.

¿Y qué diablos significa si una operación es O(n log(n))?

Tu equipo favorito ha ganado, están en la fila y hay njugadores en el equipo. Cuántos apretones de manos le tomará dar la mano a cada jugador, dado que lo hará varias veces, cuántas veces, cuántos dígitos hay en el número de jugadores n.

Nota: esto cederá n * log n to the base 10.

¿Y alguien tiene que fumar crack para escribir un O(x!)?

Eres un niño rico y en tu armario hay una gran cantidad de telas, hay xcajones para cada tipo de ropa, los cajones están uno al lado del otro, el primer cajón tiene 1 artículo, cada cajón tiene tantas telas como en el cajón. está a la izquierda y uno más, así que tienes algo como 1sombrero, 2pelucas, .. (x-1)pantalones, luego xcamisas. Ahora, de cuántas maneras puedes vestirte usando un solo artículo de cada cajón.

Nota: este ejemplo representa la cantidad de hojas en un árbol de decisión donde number of children = depth, que se realiza a través de1 * 2 * 3 * .. * x

Intento explicar dando ejemplos de código simple en C #.

Para la List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};

O (1) se parece a

return numbers.First();

O (n) se parece a

int result = 0; foreach (int num in numbers) { result += num; } return result;

O (n log (n)) se parece a

int result = 0; foreach (int num in numbers) { int index = numbers.length - 1; while (index > 1) { // yeah, stupid, but couldn''t come up with something more useful :-( result += numbers[index]; index /= 2; } } return result;

O (n ^ 2) se parece a

int result = 0; foreach (int outerNum in numbers) { foreach (int innerNum in numbers) { result += outerNum * innerNum; } } return result;

O (n!) Parece, uhm, cansado de inventar algo simple.
Pero espero que tengas el punto general?

La forma en que lo describo a mis amigos no técnicos es así:

Considere la adición de varios dígitos. Buena adición a la antigua, lápiz y papel. El tipo que aprendiste cuando tenías 7-8 años. Teniendo en cuenta dos números de tres o cuatro dígitos, puedes averiguar qué suman fácilmente.

Si te di dos números de 100 dígitos y te pregunté a qué se suman, descubrirlo sería bastante sencillo, incluso si tuvieras que usar lápiz y papel. Un niño brillante podría hacer tal adición en solo unos minutos. Esto solo requeriría unas 100 operaciones.

Ahora, considere la multiplicación de varios dígitos. Probablemente aprendiste eso alrededor de los 8 o 9 años. Usted (con suerte) hizo muchos ejercicios repetitivos para aprender la mecánica detrás de esto.

Ahora, imagina que te di esos mismos dos números de 100 dígitos y te dije que los multipliques juntos. Esta sería una tarea mucho más difícil, algo que le llevaría horas de hacer, y que probablemente no haría sin errores. La razón de esto es que (esta versión de) la multiplicación es O (n ^ 2); cada dígito en el número inferior debe ser multiplicado por cada dígito en el número superior, dejando un total de aproximadamente n ^ 2 operaciones. En el caso de los números de 100 dígitos, eso es 10,000 multiplicaciones.

La forma en que lo pienso, es que tienes la tarea de solucionar un problema causado por un malvado villano V que escoge N, y tienes que estimar cuánto más tardará en terminar tu problema cuando aumente N.

O (1) -> aumentar N realmente no hace ninguna diferencia

O (log (N)) -> cada vez que V duplica N, debe pasar una cantidad extra de tiempo T para completar la tarea. V duplica N de nuevo, y gastas la misma cantidad.

O (N) -> cada vez que V duplica N, pasas el doble de tiempo.

O (N ^ 2) -> cada vez que V duplica N, gastas 4 veces más tiempo. (¡¡¡No es justo!!!)

O (N log (N)) -> cada vez que V duplica N, pasas el doble de tiempo y un poco más.

Estos son los límites de un algoritmo; los científicos de la computación desean describir cuánto tiempo tomarán los grandes valores de N. (lo que se vuelve importante cuando se están factorizando los números que se utilizan en la criptografía; si las computadoras se aceleran en un factor de 10, ¿cuántos bits más hacen?) tiene que usarlo para asegurarse de que todavía tardará 100 años en romper su cifrado y no solo 1 año?)

Algunos de los límites pueden tener expresiones extrañas si hace una diferencia para las personas involucradas. He visto cosas como O (N log (N) log (log (N))) en algún lugar de Knuth''s Art of Computer Programming para algunos algoritmos. (No puedo recordar cuál de la cabeza)

La mayoría de los libros de Jon Bentley (por ejemplo, Programming Pearls ) cubren estas cosas de una manera muy pragmática. Esta charla dada por él incluye uno de esos análisis de una ordenación rápida.

Aunque no es del todo relevante para la pregunta, a Knuth se le ocurrió una idea interesante : enseñar notación Big-O en las clases de cálculo de la escuela secundaria, aunque esta idea me parece bastante excéntrica.

La respuesta de don.neufeld es muy buena, pero probablemente lo explique en dos partes: primero, hay una jerarquía aproximada de O () en la que se encuentran la mayoría de los algoritmos. Luego, puede ver cada uno de ellos para elaborar bocetos de lo que hacen los algoritmos típicos de esa complejidad de tiempo.

Para propósitos prácticos, los únicos O () que alguna vez parecen importar son:

  • O (1) "tiempo constante": el tiempo requerido es independiente del tamaño de la entrada. Como categoría general, incluiría algoritmos como las búsquedas de hash y Union-Find aquí, aunque ninguno de ellos sea realmente O (1).
  • O (log (n)) "logarítmico": se vuelve más lento a medida que obtiene entradas más grandes, pero una vez que su entrada es bastante grande, no cambiará lo suficiente como para preocuparse. Si su tiempo de ejecución está bien con datos de tamaño razonable, puede inundarlo con tantos datos adicionales como desee y aún así estará bien.
  • O (n) "lineal": cuanto más entrada, más tiempo lleva, en una compensación uniforme. Tres veces el tamaño de entrada tomará aproximadamente tres veces más largo.
  • O (n log (n)) "mejor que cuadrático": aumenta el tamaño de la entrada, pero sigue siendo manejable. El algoritmo es probablemente decente, es solo que el problema subyacente es más difícil (las decisiones están menos localizadas con respecto a los datos de entrada) que los problemas que se pueden resolver en tiempo lineal. Si los tamaños de entrada aumentan, no suponga que necesariamente podría manejar el doble del tamaño sin cambiar la arquitectura (por ejemplo, moviendo las cosas a los cálculos de la noche a la mañana, o no haciendo las cosas por fotograma). Está bien si el tamaño de la entrada aumenta un poco, sin embargo; sólo ten cuidado con los múltiplos.
  • O (n ^ 2) "cuadrático": en realidad solo va a funcionar hasta cierto tamaño de tu entrada, así que presta atención a qué tan grande podría ser. Además, su algoritmo puede apestar - piense con dificultad para ver si hay un algoritmo O (n log (n)) que le ofrezca lo que necesita. Una vez que estés aquí, siéntete muy agradecido por el increíble hardware con el que hemos sido dotados. No hace mucho tiempo, lo que está tratando de hacer hubiera sido imposible para todos los propósitos prácticos.
  • O (n ^ 3) "cúbico": no es cualitativamente tan diferente de O (n ^ 2). Los mismos comentarios se aplican, pero más aún. Existe una buena posibilidad de que un algoritmo más inteligente pueda reducir esta vez a algo más pequeño, por ejemplo, O (n ^ 2 log (n)) u O (n ^ 2.8 ...), pero, de nuevo, es muy probable que no valdrá la pena (Ya tiene un tamaño de entrada práctico limitado, por lo que los factores constantes que pueden requerirse para los algoritmos más inteligentes probablemente anularán sus ventajas para los casos prácticos. Además, pensar es lento; dejar que la computadora lo mastique puede ahorrarle tiempo. en general.)
  • O (2 ^ n) "exponencial": el problema es fundamentalmente computacionalmente difícil o eres un idiota. Estos problemas tienen un sabor reconocible para ellos. Sus tamaños de entrada están limitados a un límite duro bastante específico. Sabrás rápidamente si encajas en ese límite.

Y eso es. Hay muchas otras posibilidades que encajan entre estas (o son mayores que O (2 ^ n)), pero no suelen ocurrir en la práctica y no son muy diferentes cualitativamente de una de estas. Los algoritmos cúbicos ya son un poco exagerados; Solo los incluí porque los he encontrado con la frecuencia suficiente para que valga la pena mencionarlos (por ejemplo, la multiplicación de matrices).

¿Qué sucede realmente con estas clases de algoritmos? Bueno, creo que tuvo un buen comienzo, aunque hay muchos ejemplos que no encajan en estas caracterizaciones. Pero por lo anterior, yo diría que usualmente es algo como:

  • O (1): solo está mirando la mayoría de una parte de tamaño fijo de sus datos de entrada, y posiblemente ninguno de ellos. Ejemplo: el máximo de una lista ordenada.
    • O su tamaño de entrada es delimitado. Ejemplo: suma de dos números. (Tenga en cuenta que la suma de N números es un tiempo lineal).
  • O (registro n): cada elemento de tu entrada te dice lo suficiente como para ignorar una gran fracción del resto de la entrada. Ejemplo: cuando observa un elemento de matriz en la búsqueda binaria, su valor le indica que puede ignorar "la mitad" de su matriz sin mirar ninguna de ellas. O similarmente, el elemento que mira le brinda suficiente de un resumen de una fracción de la información restante que no necesitará mirar.
    • Sin embargo, no hay nada especial en las mitades: si solo puedes ignorar el 10% de tu entrada en cada paso, sigue siendo logarítmico.
  • O (n): realiza una cantidad fija de trabajo por elemento de entrada. (Pero ver más abajo).
  • O (n log (n)) - hay algunas variantes.
    • Puede dividir la entrada en dos pilas (en no más de tiempo lineal), resolver el problema de forma independiente en cada pila y luego combinar las dos pilas para formar la solución final. La independencia de las dos pilas es clave. Ejemplo: mergesort clásico recursivo.
    • Cada paso de tiempo lineal sobre los datos lo lleva a la mitad de su solución. Ejemplo: ordene rápidamente si piensa en la distancia máxima de cada elemento hasta su posición final ordenada en cada paso de partición (y sí, sé que en realidad es O (n ^ 2) debido a las opciones de pivote degenerado. Pero prácticamente hablando, cae en mi categoría O (n log (n)).
  • O (n ^ 2) - tienes que mirar cada par de elementos de entrada.
    • O no, pero crees que sí, y estás usando el algoritmo incorrecto.
  • O (n ^ 3) - um ... No tengo una breve descripción de estos. Es probablemente uno de
    • Estas multiplicando matrices
    • Estás mirando cada par de entradas, pero la operación que haces requiere mirar todas las entradas de nuevo
    • Toda la estructura gráfica de tu entrada es relevante.
  • O (2 ^ n): debe considerar cada posible subconjunto de sus entradas.

Ninguno de estos son rigurosos. Especialmente no los algoritmos de tiempo lineal (O (n)): podría dar una serie de ejemplos en los que tenga que ver todas las entradas, luego la mitad de ellas, la mitad de ellas, etc. O al revés: - Se pliegan pares de entradas, luego se reparten en la salida. Estos no se ajustan a la descripción anterior, ya que no están viendo cada entrada una vez, pero aún sale en tiempo lineal. Aún así, el 99.2% del tiempo, el tiempo lineal significa mirar cada entrada una vez.

Lo importante que la notación Big-O significa para su código es cómo se escalará cuando duplique la cantidad de "cosas" sobre las que opera. Aquí hay un ejemplo concreto:

Big-O | computations for 10 things | computations for 100 things ---------------------------------------------------------------------- O(1) | 1 | 1 O(log(n)) | 3 | 7 O(n) | 10 | 100 O(n log(n)) | 30 | 700 O(n^2) | 100 | 10000

Así que tome quicksort que es O (n log (n)) vs burbuja que es O (n ^ 2). Al ordenar 10 cosas, el orden rápido es 3 veces más rápido que el ordenamiento por burbuja. ¡Pero al ordenar 100 cosas, es 14 veces más rápido! Claramente, escoger el algoritmo más rápido es importante entonces. Cuando llega a las bases de datos con millones de filas, puede significar la diferencia entre la ejecución de su consulta en 0.2 segundos, en lugar de tomar horas.

Otra cosa a considerar es que un mal algoritmo es una cosa que la ley de Moore no puede ayudar. Por ejemplo, si tiene un cálculo científico que es O (n ^ 3) y puede calcular 100 cosas por día, duplicar la velocidad del procesador solo le da 125 cosas en un día. Sin embargo, ponga ese cálculo en O (n ^ 2) y está haciendo 1000 cosas por día.

aclaración: en realidad, Big-O no dice nada sobre el rendimiento comparativo de diferentes algoritmos en el mismo punto de tamaño específico, sino más bien sobre el rendimiento comparativo del mismo algoritmo en diferentes puntos de tamaño:

computations computations computations Big-O | for 10 things | for 100 things | for 1000 things ---------------------------------------------------------------------- O(1) | 1 | 1 | 1 O(log(n)) | 1 | 3 | 7 O(n) | 1 | 10 | 100 O(n log(n)) | 1 | 33 | 664 O(n^2) | 1 | 100 | 10000

Me gusta la respuesta de don Neufeld, pero creo que puedo agregar algo sobre O (n log n).

Un algoritmo que usa una estrategia simple de dividir y conquistar probablemente será O (log n). El ejemplo más simple de esto es encontrar algo en una lista ordenada. No empiezas por el principio y lo buscas. Vas al centro, decides si debes ir hacia atrás o hacia adelante, salta a la mitad del último lugar donde miraste y repite esto hasta que encuentres el elemento que estás buscando.

Si observa los algoritmos quicksort o mergesort, verá que ambos adoptan el enfoque de dividir la lista para dividirla por la mitad, clasificar cada mitad (utilizando el mismo algoritmo, recursivamente) y luego combinar las dos mitades. Este tipo de estrategia recursiva de dividir y conquistar será O (n log n).

Si lo piensa con cuidado, verá que quicksort realiza un algoritmo de partición O (n) en los n elementos completos, luego una partición O (n) dos veces en n / 2 elementos, luego 4 veces en n / 4 elementos, etc ... hasta que llegue a n particiones en 1 elemento (que está degenerado). El número de veces que divide n por la mitad para llegar a 1 es aproximadamente log n, y cada paso es O (n), por lo que la división recursiva y la conquista es O (n log n). Mergesort se construye a la inversa, comenzando con n recombinaciones de 1 elemento y terminando con 1 recombinación de n elementos, donde la recombinación de dos listas clasificadas es O (n).

En cuanto a fumar crack para escribir un algoritmo O (n!), Lo eres a menos que no tengas otra opción. Se cree que el problema del vendedor ambulante dado anteriormente es uno de esos problemas.

Muchos de estos son fáciles de demostrar con algo no programado, como barajar cartas.

Clasificar un mazo de cartas pasando por todo el mazo para encontrar el as de espadas, luego atravesar todo el mazo para encontrar el 2 de picas, y así sería el peor caso n ^ 2, si el mazo ya estaba ordenado al revés. Miraste todas las 52 cartas 52 veces.

En general, los algoritmos realmente malos no son necesariamente intencionales, generalmente son un mal uso de otra cosa, como llamar a un método que es lineal dentro de otro método que se repite sobre el mismo conjunto de forma lineal.

No, un algoritmo O (n) no significa que realizará una operación en cada elemento. La notación Big-O le brinda una manera de hablar sobre la "velocidad" de su algoritmo independiente de su máquina real.

O (n) significa que el tiempo que tomará su algoritmo crece linealmente a medida que aumenta su entrada. O (n ^ 2) significa que el tiempo que tarda su algoritmo crece como el cuadrado de su entrada. Etcétera.

Ok, hay algunas respuestas muy buenas aquí, pero casi todas parecen cometer el mismo error y es una que impregna el uso común.

De manera informal, escribimos que f (n) = O (g (n)) si, hasta un factor de escala y para todos los n más grandes que algunos n0, g (n) es mayor que f (n). Es decir, f (n) no crece más rápido que, o está limitado desde arriba por, g (n). Esto no nos dice nada acerca de qué tan rápido crece f (n), excepto por el hecho de que se garantiza que no será peor que g (n).

Un ejemplo concreto: n = O (2 ^ n). Todos sabemos que n crece mucho menos rápidamente que 2 ^ n, por lo que nos da derecho a decir que está limitado por la función exponencial. Hay mucho espacio entre n y 2 ^ n, por lo que no es un límite muy estrecho , pero sigue siendo un límite legítimo.

¿Por qué nosotros (científicos de computación) usamos límites en lugar de ser exactos? Debido a que a) los límites suelen ser más fáciles de probar yb) nos da una mano corta para expresar las propiedades de los algoritmos. Si digo que mi nuevo algoritmo es O (n.log n), eso significa que, en el peor de los casos, su tiempo de ejecución estará limitado desde arriba por n.log n en n entradas, lo suficientemente grande como n (aunque vea mis comentarios a continuación sobre cuándo podría no significar el peor de los casos).

Si en cambio, queremos decir que una función crece exactamente tan rápido como alguna otra función, usamos theta para hacer ese punto (escribiré T (f (n)) para significar / Theta de f (n) en markdown) . T (g (n)) es una mano corta para estar delimitada desde arriba y abajo por g (n), de nuevo, hasta un factor de escala y asintóticamente.

Eso es f (n) = T (g (n)) <=> f (n) = O (g (n)) y g (n) = O (f (n)). En nuestro ejemplo, podemos ver que n! = T (2 ^ n) porque 2 ^ n! = O (n).

¿Por qué preocuparse por esto? Porque en tu pregunta escribes ''¿alguien tendría que fumar crack para escribir una O (x!)? La respuesta es no, porque básicamente todo lo que escriba estará limitado desde arriba por la función factorial. El tiempo de ejecución de quicksort es O (n!), Simplemente no es un límite ajustado.

También hay otra dimensión de la sutileza aquí. Por lo general, estamos hablando de la entrada de caso más desfavorable cuando usamos la notación O (g (n)), por lo que estamos haciendo una declaración compuesta: en el caso de tiempo más desfavorable, no será peor que un algoritmo que tome g (n ) pasos, nuevamente modulo de escala y para n lo suficientemente grande. Pero a veces queremos hablar sobre el tiempo de ejecución de los casos promedio e incluso los mejores .

Vanilla quicksort es, como siempre, un buen ejemplo. Es T (n ^ 2) en el peor de los casos (en realidad tomará al menos n ^ 2 pasos, pero no significativamente más), pero T (n.log n) en el caso promedio, es decir, el número esperado de Los pasos son proporcionales a n.log n. En el mejor de los casos, también es T (n.log n), pero podría mejorar eso para, por ejemplo, verificar si la matriz ya estaba ordenada, en cuyo caso el mejor tiempo de ejecución del caso sería T (n).

¿Cómo se relaciona esto con su pregunta sobre las realizaciones prácticas de estos límites? Bueno, desafortunadamente, la notación O () oculta las constantes con las que tienen que lidiar las implementaciones del mundo real. Entonces, aunque podemos decir que, por ejemplo, para una operación T (n ^ 2) tenemos que visitar cada par de elementos posibles, no sabemos cuántas veces tenemos que visitarlos (excepto que no es una función de norte). Así que podríamos tener que visitar cada par 10 veces, o 10 ^ 10 veces, y la declaración T (n ^ 2) no hace ninguna distinción. Las funciones de orden inferior también están ocultas: podríamos tener que visitar cada par de elementos una vez, y cada elemento individual 100 veces, porque n ^ 2 + 100n = T (n ^ 2). La idea detrás de la notación O () es que para n lo suficientemente grande, esto no importa en absoluto porque n ^ 2 es mucho más grande que 100n que ni siquiera notamos el impacto de 100n en el tiempo de ejecución. Sin embargo, a menudo tratamos con "lo suficientemente pequeño" como para que factores constantes y así sucesivamente hagan una diferencia real y significativa.

Por ejemplo, quicksort (costo promedio T (n.log n)) y heapsort (costo promedio T (n.log n)) son algoritmos de clasificación con el mismo costo promedio; sin embargo, quicksort suele ser mucho más rápido que heapsort. Esto se debe a que heapsort hace algunas comparaciones más por elemento que quicksort.

Esto no quiere decir que la notación O () sea inútil, simplemente imprecisa. Es una herramienta bastante contundente para ejercer para n pequeña.

(Como nota final de este tratado, recuerde que la notación O () simplemente describe el crecimiento de cualquier función; no necesariamente tiene que ser tiempo, puede ser memoria, mensajes intercambiados en un sistema distribuido o la cantidad de CPU necesarias para un algoritmo paralelo)

Para entender O (n log n), recuerde que log n significa log-base-2 de n. Luego mira cada parte:

O (n) es, más o menos, cuando opera con cada elemento del conjunto.

O (log n) es cuando el número de operaciones es el mismo que el exponente al que elevas 2, para obtener el número de elementos. Una búsqueda binaria, por ejemplo, tiene que cortar el conjunto en medio log n veces.

O (n log n) es una combinación: estás haciendo algo en la línea de una búsqueda binaria para cada elemento del conjunto. Las clasificaciones eficientes a menudo funcionan haciendo un bucle por elemento, y en cada bucle hacen una buena búsqueda para encontrar el lugar correcto para poner el elemento o grupo en cuestión. Por lo tanto, n * log n.

Para ser sincero con la pregunta, respondería a la pregunta de la misma manera que respondería a un niño de 8 años.

Supongamos que un vendedor de helados prepara una cantidad de helados (por ejemplo, N) de diferentes formas dispuestas de manera ordenada. Quieres comer el helado en medio.

Caso 1: - Usted puede comer un helado solo si ha comido todos los helados más pequeños que él. Deberá comer la mitad de todos los helados preparados (entrada). La respuesta depende directamente del tamaño de la entrada. La solución será de orden o (N)

Caso 2: - Puedes comer directamente el helado en el medio.

La solución será O (1)

Caso 3: Puedes comer un helado solo si has comido todos los helados más pequeños que él y cada vez que comes un helado, permites que otro niño (niño nuevo cada vez) coma todos sus helados. El tiempo total tomado sería N + N + N ....... (N / 2) veces la solución será O (N2)

Piense en ello como apilar bloques de lego (n) verticalmente y saltar sobre ellos.

O (1) significa que en cada paso, no haces nada. La altura se mantiene igual.

O (n) significa que en cada paso, apila bloques c, donde c1 es una constante.

O (n ^ 2) significa que en cada paso, apila bloques xn c2, donde c2 es una constante y n es el número de bloques apilados.

O (nlogn) significa que en cada paso, apila c3 xnx log n bloques, donde c3 es una constante, y n es el número de bloques apilados.

Puede resultarle útil visualizarlo:

Además, en la escala LogY / LogX , las funciones n 1/2 , n, n 2 se ven como líneas rectas , mientras que en la escala LogY / X 2 n , e n , 10 n son líneas rectas yn! es linearithmic (se parece a n log n ).

Solo para responder a un par de comentarios en mi publicación anterior:

Domenic - Estoy en este sitio, y me importa. No por pedantería, sino porque nosotros, como programadores, nos importa la precisión. El uso incorrecto de la notación O () en el estilo que algunos han hecho aquí hace que carezca de significado; igual podemos decir que algo lleva n ^ 2 unidades de tiempo como O (n ^ 2) según las convenciones que se utilizan aquí. Usar la O () no agrega nada. No es solo una pequeña discrepancia entre el uso común y la precisión matemática de lo que estoy hablando, es la diferencia entre ser significativo y no.

Conozco a muchos, muchos excelentes programadores que usan estos términos con precisión. Decir ''oh, somos programadores, por lo tanto no nos importa'' abarata a toda la empresa.

onebyone - Bueno, en realidad no, aunque entiendo tu punto. No es O (1) para n arbitrariamente grande, que es una especie de definición de O (). Simplemente demuestra que O () tiene una aplicabilidad limitada para n con límite, donde preferiríamos hablar de la cantidad de pasos dados en lugar de un límite en esa cantidad.

Supongamos que tienes una computadora que podría resolver un problema de cierto tamaño. Ahora imagina que podemos duplicar el rendimiento unas cuantas veces. ¿Cuánto más grande es un problema que podemos resolver con cada duplicación?

Si podemos resolver un problema de duplicar el tamaño, eso es O (n).

Si tenemos un multiplicador que no es uno, eso es algún tipo de complejidad polinomial. Por ejemplo, si cada duplicación nos permite aumentar el tamaño del problema en aproximadamente un 40%, es O (n ^ 2), y aproximadamente un 30% sería O (n ^ 3).

Si solo añadimos al tamaño del problema, es exponencial o peor. Por ejemplo, si cada duplicación significa que podemos resolver un problema 1 más grande, es O (2 ^ n). (Esta es la razón por la que la clave de cifrado se convierte en algo imposible con las claves de tamaño razonable: una clave de 128 bits requiere aproximadamente 16 quintillones de procesamiento tanto como 64 bits).

Una cosa que no se ha tocado todavía por alguna razón:

Cuando vea algoritmos con cosas como O (2 ^ n) u O (n ^ 3) u otros valores desagradables, a menudo significa que tendrá que aceptar una respuesta imperfecta a su problema para obtener un rendimiento aceptable.

Las soluciones correctas que explotan de esta manera son comunes cuando se trata de problemas de optimización. Una respuesta casi correcta entregada en un plazo razonable es mejor que una respuesta correcta mucho después de que la máquina se haya convertido en polvo.

Considere el ajedrez: no sé exactamente cuál es la solución correcta, pero probablemente sea algo como O (n ^ 50) o incluso peor. En teoría, es imposible para cualquier computadora calcular la respuesta correcta, incluso si usa cada partícula en el universo como un elemento informático que realiza una operación en el tiempo mínimo posible para la vida del universo, aún le quedan muchos ceros . (Si una computadora cuántica puede resolverlo es otro asunto).

Una forma de pensar sobre esto es esta:

O (N ^ 2) significa que para cada elemento, estás haciendo algo con cada otro elemento, como compararlos. El tipo de burbuja es un ejemplo de esto.

O (N log N) significa que para cada elemento, está haciendo algo que solo necesita mirar el registro N de los elementos. Por lo general, esto se debe a que sabe algo sobre los elementos que le permiten tomar una decisión eficiente. Las clasificaciones más eficientes son un ejemplo de esto, como la ordenación por fusión.

O (N!) Significa hacer algo por todas las permutaciones posibles de los N elementos. ¡Un vendedor ambulante es un ejemplo de esto, donde hay N! Las formas de visitar los nodos y la solución de la fuerza bruta es observar el costo total de cada permutación posible para encontrar el óptimo.

log (n) significa crecimiento logarítmico. Un ejemplo sería dividir y conquistar algoritmos. Si tiene 1000 números ordenados en una matriz (ej. 3, 10, 34, 244, 1203 ...) y desea buscar un número en la lista (encontrar su posición), puede comenzar por verificar el valor del número en el índice 500. Si es más bajo de lo que buscas, salta a 750. Si es más alto de lo que buscas, salta a 250. Luego repites el proceso hasta que encuentres tu valor (y clave). Cada vez que saltamos la mitad del espacio de búsqueda, podemos eliminar probando muchos otros valores, ya que sabemos que el número 3004 no puede estar por encima del número 5000 (recuerde, es una lista ordenada).

n log (n) significa n * log (n).

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

Imagina una "competencia" entre dos funciones sobre x, ya que x se acerca al infinito: f (x) y g (x).

Ahora, si desde algún punto en (alguna x) una función siempre tiene un valor más alto que la otra, entonces llamemos a esta función "más rápida" 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 que g (x) = O (f (x)). f (x) plantea una especie de "límite de velocidad" de tipos para g (x), ya que eventualmente lo pasa y lo deja para siempre.

Esta no es exactamente la definición de notación de gran O , que también indica 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 ayuda 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 haber conseguido hacerlo intuitivo.

  • ¿Y alguien tiene que fumar crack para escribir una O (x!)?

No, solo usa Prolog. Si escribe un algoritmo de clasificación en Prolog simplemente describiendo que cada elemento debe ser más grande que el anterior, y deje que la marcha atrás haga la clasificación por usted, eso será O (x!). También conocido como "orden de permutación".