¿Big-O para niños de ocho años?[duplicar]
https://stackoverflow.com/questions/107165
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esta pregunta ya tiene respuesta aquí:
Estoy preguntando más sobre lo que esto significa para mi código.Entiendo los conceptos matemáticamente, pero me cuesta entender lo que significan conceptualmente.Por ejemplo, si uno realizara 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ías un conjunto de operaciones en cada elemento.¿Alguien podría completar los espacios en blanco aquí?
- ¿Qué haría exactamente 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!)?
Solución
Una forma de pensarlo es esta:
O(N^2) significa que para cada elemento, estás haciendo algo con todos los demás elementos, como compararlos.La clasificación de burbujas es un ejemplo de esto.
O(N log N) significa que para cada elemento, estás haciendo algo que solo necesita mirar el log N de los elementos.Generalmente esto se debe a que usted 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 clasificación por combinación.
O(N!) significa hacer algo para todas las posibles permutaciones de los N elementos.El vendedor ambulante es un ejemplo de esto, donde hay N!formas de visitar los nodos, y la solución de fuerza bruta es observar el costo total de cada permutación posible para encontrar la óptima.
Otros consejos
Lo más importante que significa la notación Big-O para su código es cómo escalará cuando duplique la cantidad de "cosas" en las que opera.He aquí 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
Entonces, tome la clasificación rápida, que es O (n log (n)) frente a la clasificación por burbujas, que es O (n ^ 2).Al clasificar 10 cosas, la clasificación rápida es 3 veces más rápida que la clasificación por burbujas.Pero al clasificar 100 cosas, ¡es 14 veces más rápido!Entonces, claramente es importante elegir el algoritmo más rápido.Cuando llega a bases de datos con millones de filas, puede significar la diferencia entre que su consulta se ejecute en 0,2 segundos o que tarde horas.
Otra cosa a considerar es que un mal algoritmo es algo que la ley de Moore no puede ayudar.Por ejemplo, si tienes algún cálculo científico que es O(n^3) y puede calcular 100 cosas por día, duplicar la velocidad del procesador solo te permitirá obtener 125 cosas en un día.Sin embargo, si reduce ese cálculo a O(n^2) estará haciendo 1000 cosas al 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 puntos de diferentes tamaños:
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
Puede resultarle útil visualizarlo:
También en LogY/LogX escalar las funciones norte1/2, norte, norte2 todos parecen lineas rectas, mientras tanto RegistroY/X escala 2norte, minorte, 10norte son lineas rectas y ¡norte! es linealitmico (parece norte iniciar sesión norte).
Esto puede ser demasiado matemático, pero aquí está mi intento.(I soy un matemático.)
Si algo es O(F(norte)), entonces es tiempo de ejecución norte elementos serán iguales a A F(norte) + B (medido en, digamos, ciclos de reloj u operaciones de CPU).Es clave entender que tú también tienes 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, algún preprocesamiento que realiza y que no depende del tamaño de la colección. A representa la velocidad de su algoritmo de procesamiento de artículos real.
La clave, sin embargo, es que utilices la notación O grande para calcular qué tan bien algo escalará.Entonces esas constantes realmente no importarán:Si estás tratando de descubrir cómo escalar de 10 a 10000 elementos, ¿a quién le importan los gastos generales constantes? B?De manera similar, otras preocupaciones (ver más abajo) ciertamente superarán el peso de la constante multiplicativa. A.
Entonces el verdadero negocio es F(norte).Si F no crece en absoluto con norte, p.ej. F(norte) = 1, entonces escalarás fantásticamente: tu tiempo de ejecución siempre será A + B.Si F crece linealmente con norte, es decir. F(norte) = norte, su tiempo de ejecución escalará lo mejor que se pueda esperar: si sus usuarios esperan 10 ns para 10 elementos, esperarán 10000 ns para 10000 elementos (ignorando la constante aditiva).Pero si crece más rápido, como norte2, entonces estás en problemas;Las cosas empezarán a ralentizarse demasiado cuando tengas colecciones más grandes. F(norte) = norte registro(norte) es un buen compromiso, normalmente:su operación no puede ser tan simple como para dar una escala lineal, pero ha logrado reducir las cosas de modo que escalará mucho mejor que F(norte) = norte2.
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 simplemente vamos a buscarlo.No importa si la colección tiene 10 artículos o 10000;todavía está en el índice (digamos) 3, por lo que simplemente saltamos a la ubicación 3 en la memoria.
- o(norte):recuperar un elemento de una lista enlazada.Aquí, A = 0,5, porque en promedio tendrás que revisar la mitad de la lista vinculada antes de encontrar el elemento que estás buscando.
- o(norte2):varios algoritmos de clasificación "tontos".Porque generalmente su estrategia implica, para cada elemento (norte), miras todos los demás elementos (por lo que a veces otro norte, donación norte2), luego ubíquese en el lugar correcto.
- o(norte registro(norte)):varios algoritmos de clasificación "inteligentes".Resulta que sólo necesitas mirar, digamos, 10 elementos en un 1010-Colección de elementos para ordenarte inteligentemente en relación con todos más en la colección.Porque todos los demás son también Vamos a observar 10 elementos, y el comportamiento emergente está orquestado correctamente para que sea suficiente para producir una lista ordenada.
- o(norte!):un algoritmo que "intenta todo", ya que hay (proporcionalmente a) norte!posibles combinaciones de norte elementos que pueden resolver un problema determinado.Así que simplemente recorre todas esas combinaciones, las prueba y luego se detiene cuando tiene éxito.
La respuesta de don.neufeld es muy buena, pero probablemente la explicaría en dos partes:En primer lugar, existe una jerarquía aproximada de O() en la que se encuentran la mayoría de los algoritmos.Luego, puedes mirar cada uno de ellos para crear bocetos de lo que típico los algoritmos de esa complejidad temporal lo hacen.
A efectos prácticos, las únicas O() que parecen importar son:
- O(1) "tiempo constante": el tiempo requerido es independiente del tamaño de la entrada.Como categoría aproximada, incluiría aquí algoritmos como búsquedas de hash y Union-Find, aunque ninguno de ellos sea realmente O(1).
- O(log(n)) "logarítmico": se vuelve más lento a medida que obtienes entradas más grandes, pero una vez que tu entrada se vuelve bastante grande, no cambiará lo suficiente como para preocuparte.Si su tiempo de ejecución está bien con datos de tamaño razonable, puede inundarlo con tantos datos adicionales como desee y seguirá estando bien.
- O(n) "lineal": cuantas más entradas, más tiempo lleva, en una compensación equitativa.Tres veces el tamaño de entrada tomará aproximadamente tres veces más tiempo.
- O(n log(n)) "mejor que cuadrático": aumentar el tamaño de entrada duele, pero aún es manejable.El algoritmo probablemente sea decente, sólo que el problema subyacente es más difícil (las decisiones están menos localizadas con respecto a los datos de entrada) que aquellos problemas que se pueden resolver en tiempo lineal.Si sus tamaños de entrada están aumentando, no asuma que necesariamente podría manejar el doble de tamaño sin cambiar su arquitectura (por ejemplo, moviendo cosas a cálculos por lotes durante la noche o no haciendo cosas por cuadro).Sin embargo, está bien si el tamaño de entrada aumenta un poco;solo ten cuidado con los múltiples.
- O(n^2) "cuadrático": en realidad solo funcionará hasta un cierto tamaño de su entrada, así que preste atención a qué tan grande podría llegar a ser.Además, su algoritmo puede apestar: piense detenidamente para ver si hay un algoritmo O (n log (n)) que le brinde lo que necesita.Una vez que estés aquí, siéntete muy agradecido por el increíble hardware que nos han regalado.No hace mucho, lo que usted intenta hacer habría sido imposible a todos los efectos prácticos.
- O(n^3) "cúbico" - no cualitativamente tan diferente de O(n^2).Se aplican los mismos comentarios, sólo que más.Existe una buena posibilidad de que un algoritmo más inteligente pueda reducir este tiempo a algo más pequeño, por ejemplo, O(n^2 log(n)) u O(n^2.8...), pero, de nuevo, hay una buena posibilidad de que No valdrá la pena.(Ya está limitado en el tamaño de su entrada práctica, por lo que los factores constantes que pueden ser necesarios para los algoritmos más inteligentes probablemente anularán sus ventajas en casos prácticos.Además, el pensamiento es lento;dejar que la computadora lo analice puede ahorrarle tiempo en general.)
- O(2^n) "exponencial": el problema es fundamentalmente difícil desde el punto de vista computacional o estás siendo un idiota.Estos problemas tienen un sabor reconocible.Los tamaños de entrada están limitados a un límite estricto 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 ocurren con frecuencia en la práctica y no son cualitativamente muy diferentes de una de ellas.Los algoritmos cúbicos ya son un poco exagerados;Sólo los incluí porque los he encontrado con suficiente frecuencia como para que valga la pena mencionarlos (por ejemplo, multiplicación de matrices).
¿Qué está pasando realmente con estas clases de algoritmos?Bueno, creo que tuviste un buen comienzo, aunque hay muchos ejemplos que no encajarían en estas caracterizaciones.Pero para lo anterior, diría que normalmente es algo como:
- O(1): solo está viendo como máximo una porción 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 está limitado.Ejemplo:suma de dos números.(Tenga en cuenta que la suma de N números es tiempo lineal).
- O(log n): cada elemento de su entrada le dice lo suficiente como para ignorar una gran fracción del resto de la entrada.Ejemplo:cuando observa un elemento de matriz en una búsqueda binaria, su valor le indica que puede ignorar "la mitad" de su matriz sin mirar nada de él.O de manera similar, el elemento que mira le brinda un resumen suficiente de una fracción de la entrada restante que no necesitará mirarlo.
- 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)): existen algunas variantes.
- Puede dividir la entrada en dos pilas (en no más de un 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 los dos pilotes es clave.Ejemplo:mergesort recursivo clásico.
- Cada paso de tiempo lineal sobre los datos le lleva a la mitad del camino hacia su solución.Ejemplo:clasificación rápida si piensa en términos de la distancia máxima de cada elemento a su posición ordenada final en cada paso de partición (y sí, sé que en realidad es O(n^2) debido a elecciones de pivote degeneradas.Pero en la práctica, entra en mi categoría O(n log(n)).
- O(n^2): debes observar cada par de elementos de entrada.
- O no lo haces, pero crees que sí y estás usando el algoritmo equivocado.
- O(n^3) - eh...No tengo una caracterización ágil de estos.Probablemente sea uno de:
- Estas multiplicando matrices
- Estás mirando cada par de entradas, pero la operación que realizas requiere mirar todas las entradas nuevamente.
- toda la estructura gráfica de su entrada es relevante
- O(2^n): debe considerar todos los subconjuntos posibles de sus entradas.
Ninguno de estos es riguroso.Especialmente no algoritmos de tiempo lineal (O (n)):Se me podrían ocurrir varios ejemplos en los que hay que mirar todas las entradas, luego la mitad, luego la mitad, etc.O al revés: junta pares de entradas y luego recurre a la salida.Estos no se ajustan a la descripción anterior, ya que no estás mirando cada entrada una vez, pero aún así sale en tiempo lineal.Aún así, el 99,2% de las veces, el tiempo lineal significa mirar cada entrada una vez.
Muchos de estos son fáciles de demostrar con algo que no sea de programación, como barajar cartas.
Ordenar una baraja de cartas revisando toda la baraja para encontrar el as de espadas, luego revisando toda la baraja para encontrar el 2 de espadas, y así sucesivamente sería el peor de los casos n^2, si la baraja ya estuviera ordenada al revés.Miraste las 52 cartas 52 veces.
En general, los algoritmos realmente malos no son necesariamente intencionales, comúnmente son un mal uso de otra cosa, como llamar a un método que es lineal dentro de algún otro método que se repite linealmente en el mismo conjunto.
Ok, hay algunas respuestas muy buenas aquí, pero casi todas parecen cometer el mismo error y es un error que está generalizado en el uso común.
Informalmente, escribimos que f(n) = O( g(n) ) si, hasta un factor de escala y para todo n mayor que algún n0, g(n) es más grande que f(n).Es decir, f(n) no crece más rápido que, o es delimitado desde arriba por, gramo(norte).Esto no nos dice nada sobre qué tan rápido crece f(n), salvo el hecho de que se garantiza que no será peor que g(n).
Un ejemplo concreto:norte = O (2 ^ norte).Todos sabemos que n crece mucho menos rápido que 2^n, 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 muy ajustado obligado, pero sigue siendo un límite legítimo.
¿Por qué nosotros (los informáticos) utilizamos límites en lugar de ser exactos?Porque a) los límites suelen ser más fáciles de demostrar yb) nos da una forma abreviada de 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, para n lo suficientemente grande (aunque vea mis comentarios a continuación). sobre cuándo podría no decir 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 dejar claro ese punto (escribiré T( f(n) ) para significar heta de f(n) en rebajas).T( g(n) ) es una abreviatura de estar delimitado desde encima y por debajo por g(n), nuevamente, hasta un factor de escala y asintóticamente.
Es decir, 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 escribe estará limitado desde arriba por la función factorial.El tiempo de ejecución de la ordenación rápida es O(n!), simplemente no es un límite estricto.
También hay aquí otra dimensión de sutileza.Normalmente estamos hablando de la entrada del peor caso cuando usamos la notación O( g(n) ), de modo que estamos haciendo una declaración compuesta:en el peor de los casos, el tiempo de ejecución no será peor que un algoritmo que toma g(n) pasos, nuevamente escalado de módulo y para n lo suficientemente grande.Pero a veces queremos hablar del tiempo de ejecución del promedio e incluso mejor casos.
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 pasos es proporcional a n.log n.En el mejor de los casos, también es T(n.log n), pero podría mejorarlo, por ejemplo, verificando si la matriz ya estaba ordenada, en cuyo caso el mejor tiempo de ejecución 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 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 posible de elementos, no sabemos cuántas veces tenemos que visitarlos (excepto que no es una función de norte).Entonces podríamos tener que visitar cada par 10 veces, o 10^10 veces, y la declaración T(n^2) no hace 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 se vuelve 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 n "suficientemente pequeñas" de modo que factores constantes, etc., marcan una diferencia real y significativa.
Por ejemplo, la clasificación rápida (costo promedio T (n.log n)) y la clasificación en montón (costo promedio T (n.log n)) son algoritmos de clasificación con el mismo costo promedio; sin embargo, la clasificación rápida suele ser mucho más rápida que la clasificación en montón.Esto se debe a que Heapsort realiza 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 utilizar con 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, podría ser memoria, mensajes intercambiados en un sistema distribuido o la cantidad de CPU necesarias para un algoritmo paralelo.)
Intento explicarlo dando ejemplos de código simples en C#.
Para List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O(1) parece
return numbers.First();
O(n) parece
int result = 0;
foreach (int num in numbers)
{
result += num;
}
return result;
O(n log(n)) parece
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) parece
int result = 0;
foreach (int outerNum in numbers)
{
foreach (int innerNum in numbers)
{
result += outerNum * innerNum;
}
}
return result;
O(n!) parece, uhm, demasiado cansado para pensar en algo simple.
Pero espero que entiendas el punto general.
La forma en que se lo describo a mis amigos no técnicos es así:
Considere la suma de varios dígitos.Buena adición a la antigua usanza de lápiz y papel.Del tipo que aprendiste cuando tenías 7 u 8 años.Dados dos números de tres o cuatro dígitos, puedes averiguar cuánto suman con bastante facilidad.
Si te diera dos números de 100 dígitos y te preguntara cuánto suman, calcularlo sería bastante sencillo, incluso si tuvieras que usar lápiz y papel.Un niño brillante podría hacer esa adición en sólo unos minutos.Esto sólo requeriría unas 100 operaciones.
Ahora, considere la multiplicación de varios dígitos.Probablemente lo aprendiste alrededor de los 8 o 9 años.(Con suerte) hiciste 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 multiplicaras.Esto sería mucho, mucho tarea más difícil, algo que le llevaría horas hacer y que probablemente no podría hacer sin cometer errores.La razón de esto es que (esta versión de) la multiplicación es O(n^2);cada dígito del número inferior debe multiplicarse por cada dígito del número superior, dejando un total de aproximadamente n ^ 2 operaciones.En el caso de los números de 100 dígitos, son 10.000 multiplicaciones.
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 independientemente de su máquina real.
O(n) significa que el tiempo que tardará 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.
La forma en que lo pienso es que tienes la tarea de solucionar un problema causado por un villano malvado V que elige N, y tienes que estimar cuánto tiempo tomará terminar tu problema cuando aumente N.
O(1) -> aumentar N realmente no hace ninguna diferencia
O(log(N)) -> cada vez que V duplica N, debes dedicar una cantidad adicional de tiempo T para completar la tarea.V duplica N nuevamente 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, pasas 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.
Éstos son límites de un algoritmo;Los informáticos quieren describir cuánto tiempo llevará obtener valores grandes de N.(lo cual se vuelve importante cuando se factorizan números que se usan en criptografía: si las computadoras se aceleran en un factor de 10, ¿cuántos bits más tienes que usar para asegurar que les tomará 100 años romper tu cifrado y no solo 1 año?)
Algunos de los límites pueden tener expresiones extrañas si eso hace una diferencia para las personas involucradas.He visto cosas como O(N log(N) log(log(N))) en algún lugar del Arte de programación informática de Knuth para algunos algoritmos.(no recuerdo cuál de mi cabeza)
Una cosa que aún no se ha tocado por alguna razón:
Cuando ve 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 surgen de esta manera son comunes cuando se trata de problemas de optimización.Una respuesta casi correcta entregada en un período de tiempo razonable es mejor que una respuesta correcta entregada mucho después de que la máquina se haya convertido en polvo.
Consideremos el ajedrez:No sé exactamente cuál se considera la solución correcta, pero probablemente sea algo así como O(n^50) o incluso peor.Es teóricamente imposible que cualquier computadora calcule la respuesta correcta; incluso si usas cada partícula del universo como elemento computacional realizando una operación en el mínimo tiempo posible para la vida del universo, todavía te quedan muchos ceros. .(Que una computadora cuántica pueda resolverlo es otra cuestión).
La "intuición" detrás de Big-O
Imagine una "competencia" entre dos funciones sobre x, cuando x se acerca al infinito:f(x) y g(x).
Ahora, si desde algún punto en adelante (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 g(x) = O(f(x)).f(x) plantea una especie de "límite de velocidad" para g(x), ya que eventualmente lo sobrepasa y lo deja atrás para siempre.
Esta no es exactamente la definición de notación O grande, que también establece que f(x) sólo tiene que ser mayor que C*g(x) para alguna constante C (que es solo otra forma de decir que no puedes ayudar a g(x) a ganar la competencia multiplicándolo por un factor constante: f(x) siempre ganará al final).La definición formal también utiliza valores absolutos.Pero espero haber logrado 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 deja que el retroceso haga la clasificación por usted, eso será O(x!).También conocido como "ordenación por permutación".
Me gusta la respuesta de don neufeld, pero creo que puedo agregar algo sobre O (n log n).
Un algoritmo que utiliza 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 desde el principio y lo buscas.Vas al medio, decides si debes retroceder o avanzar, saltas hasta la mitad del camino hasta el último lugar donde buscaste y repites esto hasta encontrar el elemento que estás buscando.
Si observa los algoritmos de clasificación rápida o de combinación, verá que ambos adoptan el enfoque de dividir la lista que se va a ordenar por la mitad, ordenar cada mitad (usando el mismo algoritmo, de forma recursiva) y luego recombinar las dos mitades.este tipo de recursivo La estrategia de dividir y conquistar será O (n log n).
Si lo piensas detenidamente, verás que la clasificación rápida 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 llegar a n particiones en 1 elemento (que está degenerado).El número de veces que divides n por la mitad para llegar a 1 es aproximadamente log n, y cada paso es O(n), por lo que el divide y vencerás recursivo es O(n log n).Mergesort se construye al revés, comenzando con n recombinaciones de 1 elemento y terminando con 1 recombinación de n elementos, donde la recombinación de dos listas ordenadas es O(n).
En cuanto a fumar crack para escribir un algoritmo O(n!), lo es a menos que no tenga otra opción.Se cree que el problema del viajante mencionado anteriormente es uno de esos problemas.
La mayoría de los libros de Jon Bentley (p. ej. Perlas de programación) cubren este tipo de cosas de una manera realmente pragmática. esta charla dado por él incluye uno de esos análisis de clasificación rápida.
Si bien no es del todo relevante para la pregunta, a Knuth se le ocurrió una idea interesante:enseñar notación O grande en las clases de cálculo de la escuela secundaria, aunque encuentro esta idea bastante excéntrica.
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 sigue siendo la misma.
O(n) significa que en cada paso, apilas c bloques, donde c1 es una constante.
O(n^2) significa que en cada paso, apilas bloques c2 x n, donde c2 es una constante y n es el número de bloques apilados.
O(nlogn) significa que en cada paso, apilas bloques c3 x n x log n, donde c3 es una constante y n es el número de bloques apilados.
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 en cada elemento del conjunto.
O(log n) es cuando el número de operaciones es igual al exponente al que elevas 2, para obtener el número de elementos.Una búsqueda binaria, por ejemplo, tiene que cortar el conjunto a la mitad log n veces.
O(n log n) es una combinación: estás haciendo algo parecido a una búsqueda binaria para cada elemento del conjunto.Las clasificaciones eficientes a menudo operan haciendo un bucle por artículo, y en cada bucle haciendo una buena búsqueda para encontrar el lugar correcto para colocar el artículo o grupo en cuestión.Por tanto n * log n.
Solo para responder al par de comentarios en mi publicación anterior:
domenico - Estoy en este sitio y me importa.No por pedantería, sino porque nosotros, como programadores, normalmente nos preocupamos por la precisión.El uso incorrecto de la notación O( ) en el estilo que algunos han hecho aquí le resta sentido;También podemos decir que algo toma n^2 unidades de tiempo como O(n^2) según las convenciones utilizadas aquí.Usar O( ) no agrega nada.No me refiero sólo a una pequeña discrepancia entre el uso común y la precisión matemática, sino a la diferencia entre tener significado y no tenerlo.
Conozco muchísimos programadores excelentes que utilizan estos términos con precisión.Decir "oh, somos programadores, por lo tanto no nos importa" abarata toda la empresa.
uno a uno - 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 acotado, donde preferiríamos hablar del número de pasos dados en lugar de un límite para ese número.
Dígale a su niño de ocho años que log(n) significa el número de veces que tiene que cortar una longitud de n log en dos para que alcance el tamaño n=1:p
O (n log n) generalmente está clasificando o (n^2) generalmente compara todos los pares de elementos
Supongamos que tiene una computadora que puede resolver un problema de cierto tamaño.Ahora imagina que podemos duplicar el rendimiento varias veces.¿Qué problema tan grande podemos resolver con cada duplicación?
Si podemos resolver un problema del doble de tamaño, ese es O(n).
Si tenemos algún multiplicador que no es uno, es algún tipo de complejidad polinómica.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 simplemente aumentamos el tamaño del problema, es exponencial o peor.Por ejemplo, si cada duplicación significa que podemos resolver un problema 1 mayor, es O(2^n).(Esta es la razón por la que forzar una clave de cifrado por fuerza bruta se vuelve efectivamente imposible con claves de tamaño razonable:una clave de 128 bits requiere alrededor de 16 quintillones de veces más procesamiento que una de 64 bits).
¿Recuerdas la fábula de la tortuga y la liebre (tortuga y conejo)?
A largo plazo, gana la tortuga, pero a corto plazo gana la liebre.
Eso es como O(logN) (tortuga) vs.O(N) (liebre).
Si dos métodos difieren en su O grande, entonces hay un nivel de N en el que uno de ellos ganará, pero la O grande no dice nada sobre qué tan grande es ese N.
Para ser sincero con la pregunta formulada, responderí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 varios helados (digamos N) de diferentes formas dispuestos de forma ordenada.Quieres comerte el helado que está en el medio.
Caso 1 :- Puede comer un helado solo si ha comido todos los helados más pequeños de lo que tendrá que comer la mitad de todos los helados preparados (entrada). La respuesta depende directamente del tamaño de la solución de entrada será de orden o (NORTE)
Caso 2: Puedes comerte el helado directamente en el medio.
La solución será O(1)
Caso 3:Puede comer un helado solo si ha comido todos los helados más pequeños que él y cada vez que come 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) la solución de veces será O (N2)
log(n) significa crecimiento logarítmico.Un ejemplo serían los algoritmos de divide y vencerás.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 verificando el valor del número en el índice 500.Si es inferior a lo que buscas, salta a 750.Si es superior a 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 descartar 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) entonces significa n * log(n).
Intentaré escribir una explicación para un niño real de ocho años, aparte de términos técnicos y nociones matemáticas.
¿Qué sería exactamente un
O(n^2)operación hacer?
Si estás en una fiesta y hay n personas del grupo, incluyéndote a ti.¿Cuántos apretones de manos se necesitan para que todos hayan dado la mano a todos los demás, dado que las personas probablemente olvidarían a quién dieron la mano en algún momento?
Nota:esto se aproxima a un rendimiento simplex n(n-1) que está lo suficientemente cerca de n^2.
¿Y qué diablos significa si una operación es
O(n log(n))?
Tu equipo favorito ha ganado, están haciendo fila y hay n jugadores del equipo.¿Cuántos apretones de manos se necesitarían para dar la mano a cada jugador, dado que le darás la mano a cada uno varias veces, cuántas veces, cuántos dígitos hay en el número de jugadores? n.
Nota:esto producirá 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 mucha ropa, hay x cajones para cada tipo de ropa, los cajones están uno al lado del otro, el primer cajón tiene 1 prenda, cada cajón tiene tantos paños como en el cajón de su izquierda y uno más, entonces tienes algo como 1 sombrero, 2 pelucas,.. (x-1) pantalones, entonces x camisas.Ahora, ¿de cuántas maneras puedes vestirte usando un solo artículo de cada cajón?
Nota:este ejemplo representa cuántas hojas en un árbol de decisión donde number of children = depth, que se realiza a través de 1 * 2 * 3 * .. * x
