algorithm - resueltos - notacion theta

¿Qué es una explicación simple en inglés de la notación "Big O"? (30)

¿Qué es una explicación simple en inglés de la notación "Big O"?

Nota muy rápida:

La O en "Big O" se refiere a "Orden" (o, precisamente, "orden de"),
por lo que podría tener su idea literalmente de que se usa para ordenar algo y compararlos.

"Big O" hace dos cosas:
1. Calcula cuántos pasos del método aplica tu computadora para realizar una tarea.
2. ¿Facilita el proceso para comparar con otros para determinar si es bueno o no?
3. "Big O ''logra los dos anteriores con los estandarizados Notations.
Hay siete notaciones más usadas.
1. O (1), significa que su computadora hace una tarea con el 1paso, es excelente, Número 1 ordenado
2. O (logN), significa que su computadora completa una tarea con logNpasos, está bien, no.
3. O (N), termina una tarea con N pasos, su feria, Orden No.3
4. O (NlogN), finaliza una tarea con O(NlogN)pasos, no es bueno, Número de pedido.4
5. O (N ^ 2), haga una tarea con N^2pasos, es malo, Orden No.5
6. O (2 ^ N), haz una tarea con 2^Npasos, es horrible, Orden No.6
7. O (N!), Haz una tarea con N!pasos, es terrible, Orden No.7

Suponga que obtiene notación O(N^2), no solo está claro que el método toma N * N pasos para realizar una tarea, sino que también ve que no es bueno O(NlogN)desde su clasificación.

Tenga en cuenta el orden al final de la línea, solo para su mejor comprensión. Hay más de 7 anotaciones si se consideran todas las posibilidades.

En CS, el conjunto de pasos para realizar una tarea se llama algoritmos.
En Terminología, la notación Big O se utiliza para describir el rendimiento o la complejidad de un algoritmo.

Además, Big O establece el peor de los casos o mide los pasos de Upper Bound.
Puede referirse a Big-Ω (Big-Omega) para el mejor caso.

Notación Big-Ω (Big-Omega) (artículo) | academia Khan

Resumen
"Big O" describe el rendimiento del algoritmo y lo evalúa.
o abordarlo formalmente, "Big O" clasifica los algoritmos y estandariza el proceso de comparación.

Preferiría la menor definición formal posible y las matemáticas simples.

" ¿Qué es una explicación simple en inglés de Big O? Con la menor definición formal posible y matemáticas simples " .

Una pregunta tan simple y breve parece merecer al menos una respuesta igualmente breve, como la que un estudiante podría recibir durante la tutoría.

La notación Big O simplemente indica cuánto tiempo * puede ejecutarse un algoritmo, en términos de solo la cantidad de datos de entrada **.

(* en un maravilloso sentido del tiempo sin unidades !)
(** que es lo que importa, porque la gente siempre querrá más , ya sea que viva hoy o mañana)

Bueno, ¿qué tiene de maravilloso la notación Big O si eso es lo que hace?

En términos prácticos, el análisis de Big O es tan útil e importante debido a Big O pone el foco en ángulo recto en el algoritmo propia complejidad y por completo caso omiso de cualquier cosa que no es más que una constante de proporcionalidad, como un motor de JavaScript, la velocidad de una CPU, la conexión a Internet, y todas esas cosas que se convierten rápidamente llegar a ser tan ridículamente anticuada como un Modelo T . Big O se centra en el rendimiento solo en la forma en que importa tanto para las personas que viven en el presente como en el futuro.
La notación Big O también destaca directamente el principio más importante de la programación / ingeniería de computadoras, el hecho que inspira a todos los buenos programadores a seguir pensando y soñando: la única manera de lograr resultados más allá del avance lento de la tecnología es inventar un mejor algoritmo .

¿Qué es una explicación simple en inglés de Big O? Con la menor definición formal posible y matemáticas simples.

Una explicación en inglés sencillo de la necesidad de una notación Big-O:

Cuando programamos, estamos tratando de resolver un problema. Lo que codificamos se llama algoritmo. La notación Big O nos permite comparar el peor desempeño de caso de nuestros algoritmos de una manera estandarizada. Las especificaciones de hardware varían con el tiempo y las mejoras en el hardware pueden reducir el tiempo de ejecución de los algoritmos. Pero reemplazar el hardware no significa que nuestro algoritmo mejore o mejore con el tiempo, ya que nuestro algoritmo sigue siendo el mismo. Entonces, para permitirnos comparar diferentes algoritmos, para determinar si uno es mejor o no, usamos la notación Big O.

Una explicación en inglés sencillo de qué es la notación Big O:

No todos los algoritmos se ejecutan en la misma cantidad de tiempo y pueden variar según el número de elementos en la entrada, lo que llamaremos n . En base a esto, consideramos el peor análisis de casos, o un límite superior del tiempo de ejecución a medida que n se hace más y más grande. Debemos estar conscientes de lo que es n , porque muchas de las notaciones de Big O hacen referencia a él.

Prefacio

Algoritmo : procedimiento / fórmula para resolver un problema.

¿Cómo analizar los algoritmos y cómo podemos comparar los algoritmos entre sí?

Ejemplo: se le pide a usted y un amigo que creen una función para sumar los números de 0 a N. Se le ocurre f (x) y su amigo se le ocurre con g (x). Ambas funciones tienen el mismo resultado, pero un algoritmo diferente. Para comparar objetivamente la eficiencia de los algoritmos, utilizamos la notación Big-O .

Notación Big-O: describe qué tan rápido crecerá el tiempo de ejecución en relación con la entrada a medida que la entrada sea arbitrariamente grande.

3 puntos clave:

Compare qué tan rápido crece el tiempo de ejecución NO compare los tiempos de ejecución exactos (depende del hardware)
Solo preocupado por el tiempo de ejecución crecer en relación con la entrada (n)
A medida que n se hace arbitrariamente grande, enfóquese en los términos que crecerán más rápido a medida que n se haga grande (piense en el infinito) AKA análisis asintótico

Complejidad del espacio: aparte de la complejidad del tiempo, también nos preocupa la complejidad del espacio (la cantidad de memoria / espacio que utiliza un algoritmo). En lugar de verificar el tiempo de las operaciones, verificamos el tamaño de la asignación de memoria.

La notación Big-O (también llamada notación de "crecimiento asintótico") es la forma en que se ven las funciones cuando se ignoran los factores constantes y las cosas cercanas al origen . Lo usamos para hablar de cómo se escala la cosa .

Lo esencial

para "suficientemente" grandes entradas ...

f(x) ∈ O(upperbound) significa que f "no crece más rápido que" upperbound
f(x) ∈ Ɵ(justlikethis) significa f "crece exactamente igual que" justlikethis
f(x) ∈ Ω(lowerbound) significa que f "no crece más lento que" lowerbound

La notación big-O no se preocupa por los factores constantes: se dice que la función 9x² "crece exactamente igual que" 10x² . La notación asintótica big-O tampoco se preocupa por las cosas no asintóticas ("cosas cercanas al origen" o "qué sucede cuando el tamaño del problema es pequeño"): se dice que la función 10x² "crece exactamente como" 10x² - x + 2 .

¿Por qué querrías ignorar las partes más pequeñas de la ecuación? Porque se vuelven completamente enanos por las grandes partes de la ecuación al considerar escalas cada vez más grandes; Su contribución se hace enana e irrelevante. (Ver sección de ejemplo).

Dicho de otra manera, se trata de la proporción a medida que avanza hasta el infinito. Si divide el tiempo real que toma por la O(...) , obtendrá un factor constante en el límite de entradas grandes. Intuitivamente esto tiene sentido: las funciones se "escalan" una a la otra si puedes multiplicar una para obtener la otra. Es decir, cuando decimos ...

actualAlgorithmTime(N) ∈ O(bound(N)) e.g. "time to mergesort N elements is O(N log(N))"

... esto significa que para los tamaños de problema N "suficientemente grandes" (si ignoramos cosas cercanas al origen), existe una constante (por ejemplo, 2.5, completamente inventada) tal que:

actualAlgorithmTime(N) e.g. "mergesort_duration(N) " ────────────────────── < constant ───────────────────── < 2.5 bound(N) N log(N)

Hay muchas opciones de constante; a menudo, la "mejor" elección se conoce como el "factor constante" del algoritmo ... pero a menudo lo ignoramos como si ignoráramos los términos no más importantes (consulte la sección Factores constantes para saber por qué no importan). También puede pensar en la ecuación anterior como un límite que dice " En el peor de los casos, el tiempo que toma nunca será peor que aproximadamente N*log(N) , dentro de un factor de 2.5 (un factor constante que no usamos). t se preocupa mucho por) ".

En general, O(...) es el más útil porque a menudo nos preocupamos por el peor comportamiento. Si f(x) representa algo "malo" como el uso del procesador o la memoria, entonces " f(x) ∈ O(upperbound) " significa que " upperbound es el peor escenario del uso del procesador / memoria".

Aplicaciones

Como una construcción puramente matemática, la notación big-O no se limita a hablar sobre el tiempo de procesamiento y la memoria. Puede usarlo para discutir los asintóticos de cualquier cosa donde la escala sea significativa, como por ejemplo:

el número de posibles apretones de manos entre N personas en una fiesta ( Ɵ(N²) , específicamente N(N-1)/2 , pero lo que importa es que "escala como" N² )
Número probable de personas que han visto algún tipo de marketing viral en función del tiempo.
Cómo se escala la latencia del sitio web con el número de unidades de procesamiento en una CPU o GPU o un grupo de computadoras
cómo la salida de calor se escala en la CPU muere en función del conteo de transistores, voltaje, etc.
cuánto tiempo necesita un algoritmo para ejecutarse, en función del tamaño de entrada
la cantidad de espacio que debe ejecutar un algoritmo, en función del tamaño de entrada

Ejemplo

Para el ejemplo anterior de apretón de manos, todos en una habitación dan la mano a todos los demás. En ese ejemplo, #handshakes ∈ Ɵ(N²) . ¿Por qué?

Retroceda un poco: el número de apretones de manos es exactamente n-elija-2 o N*(N-1)/2 (cada una de N personas sacude las manos de otras personas de N-1, pero este doble conteo de apretones de manos se divide por 2):

Sin embargo, para un gran número de personas, el término lineal N es enano y contribuye efectivamente a 0 en la proporción (en la tabla: la fracción de cuadros vacíos en la diagonal sobre el total de cajas se reduce a medida que aumenta el número de participantes). Por lo tanto, el comportamiento de escalamiento es order N² , o el número de apretones de manos "crece como N²".

#handshakes(N) ────────────── ≈ 1/2 N²

Es como si las casillas vacías en la diagonal del gráfico (marcas de verificación N * (N-1) / 2) no estuvieran allí (marcas ^de verificación N ² asintóticamente).

(digresión temporal de "inglés simple" :) Si quisiera probárselo usted mismo, podría realizar un álgebra simple en la proporción para dividirla en múltiples términos ( lim significa "considerado en el límite de", simplemente ignórelo si no lo has visto, es solo una notación de "y N es realmente muy grande"):

N²/2 - N/2 (N²)/2 N/2 1/2 lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2 N→∞ N² N→∞ N² N² N→∞ 1 ┕━━━┙ this is 0 in the limit of N→∞: graph it, or plug in a really large number for N

tl; dr: El número de ''apretones de manos'' parece ser ''x² tanto para valores grandes, que si tuviéramos que escribir la proporción # apretones de manos / x², el hecho de que no necesitamos exactamente x2 apretones de manos no aparecería en el decimal por un tiempo arbitrariamente grande.

por ejemplo, para x = 1million, ratio # apretones de manos / x²: 0.499999 ...

Intuición del edificio

Esto nos permite hacer afirmaciones como ...

"Para el tamaño de entrada suficientemente grande = N, no importa cuál sea el factor constante, si doblo el tamaño de entrada ...

... Duplico el tiempo que lleva un algoritmo O (N) ("tiempo lineal") ".
N → (2N) = 2 ( N )
... Doble cuadrado (cuadruplicando) el tiempo que toma un algoritmo O (N²) ("tiempo cuadrático") (por ejemplo, un problema 100x tan grande toma 100² = 10000x tanto tiempo ... posiblemente insostenible)
N² → (2N) ² = 4 ( N² )
... Doble cubículo (octuple) el tiempo que tarda un algoritmo O (N³) ("tiempo cúbico") " (por ejemplo, un problema 100x tan grande toma 100³ = 1000000x tanto tiempo ... muy insostenible)
cN³ → c (2N) ³ = 8 ( cN³ )
... agrego una cantidad fija al tiempo que lleva el algoritmo O (log (N)) ("tiempo logarítmico") " (¡barato!)
c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (cantidad fija) + ( c log (N) )
... No cambio el tiempo que lleva un algoritmo O (1) ("tiempo constante") " (¡el más barato!)
c * 1 → c * 1
... I "(básicamente) doble" el tiempo que tarda un algoritmo O (N log (N)). " (Bastante común)
es menor que O (N ^1.000001 ), que podría estar dispuesto a llamar básicamente lineal
... Incremento ridículamente el tiempo que toma un algoritmo O (2 ^N ) ("tiempo exponencial"). " (Duplicaría (o triplicaría, etc.) el tiempo simplemente aumentando el problema en una sola unidad)
2 ^N → 2 ^2N = (4 ^N ) ............ puesto de otra manera ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[para los inclinados matemáticamente, puedes pasar el mouse sobre los spoilers para las notas de orientación menores]

(con crédito a https://.com/a/487292/711085 )

(técnicamente, el factor constante podría ser importante en algunos ejemplos más esotéricos, pero he expresado las cosas más arriba (por ejemplo, en log (N)) de manera que no lo hace)

Estas son las órdenes de crecimiento de pan y mantequilla que los programadores y los científicos informáticos aplicados utilizan como puntos de referencia. Ellos ven estos todo el tiempo. (Entonces, mientras que técnicamente podría pensar que "duplicar la entrada hace que un algoritmo O (√N) sea 1.414 veces más lento," es mejor pensar que "es peor que logarítmico pero mejor que lineal").

Factores constantes

Por lo general, no nos importa cuáles son los factores constantes específicos, porque no afectan la forma en que crece la función. Por ejemplo, dos algoritmos pueden tardar O(N) en completarse, pero uno puede ser dos veces más lento que el otro. Por lo general, no nos importa demasiado a menos que el factor sea muy grande, ya que la optimización es un negocio complicado (¿ cuándo es prematura la optimización? ); Además, el simple hecho de elegir un algoritmo con una mejor O grande a menudo mejorará el rendimiento en órdenes de magnitud.

Algunos algoritmos asintóticamente superiores (p. Ej., Una ordenación no comparativa O(N log(log(N))) pueden tener un factor constante tan grande (p. Ej. 100000*N log(log(N)) ), o una sobrecarga que es relativamente grande como O(N log(log(N))) con un + 100*N oculto, que rara vez vale la pena usar incluso en "big data".

Por qué O (N) es a veces lo mejor que puedes hacer, es decir, por qué necesitamos estructuras de datos

O(N) algoritmos O(N) son, en cierto sentido, los "mejores" algoritmos si necesita leer todos sus datos. El mismo acto de leer un montón de datos es una operación O(N) . Por lo general, cargarlo en la memoria es O(N) (o más rápido si tiene soporte de hardware, o no tiene tiempo si ya ha leído los datos). Sin embargo, si toca o incluso mira cada pieza de datos (o incluso cualquier otra pieza de datos), su algoritmo tomará O(N) tiempo para realizar esta búsqueda. Indique cuánto tiempo lleva su algoritmo real, será al menos O(N) porque pasó ese tiempo mirando todos los datos.

Lo mismo puede decirse del mero hecho de escribir . Todos los algoritmos que imprimen N cosas tomarán N tiempo, porque la salida es al menos tan larga (por ejemplo, imprimir todas las permutaciones (formas de reorganizar) un conjunto de N naipes es factorial: O(N!) ).

Esto motiva el uso de estructuras de datos : una estructura de datos requiere leer los datos solo una vez (generalmente O(N) ), más una cantidad arbitraria de preprocesamiento (por ejemplo, O(N) u O(N log(N)) u O(N²) ) que tratamos de mantener pequeño. Posteriormente, modificar la estructura de datos (inserciones / eliminaciones / etc.) y realizar consultas sobre los datos lleva muy poco tiempo, como O(1) u O(log(N)) . ¡Entonces procedes a hacer un gran número de consultas! En general, cuanto más trabajo esté dispuesto a hacer antes, menos trabajo tendrá que hacer más adelante.

Por ejemplo, supongamos que tenía las coordenadas de latitud y longitud de millones de segmentos de carreteras y quería encontrar todas las intersecciones de las calles.

Método ingenuo: si tuviera las coordenadas de una intersección de calles y quisiera examinar las calles cercanas, tendría que recorrer los millones de segmentos cada vez, y verificar cada una de ellas para verificar su adyacencia.
Si solo necesitara hacer esto una vez, no sería un problema tener que hacer el método ingenuo de trabajo O(N) solo una vez, pero si quiere hacerlo muchas veces (en este caso, N veces, una vez para cada segmento), tendríamos que hacer trabajo O(N²) , o 1000000² = 1000000000000 operaciones. No es bueno (una computadora moderna puede realizar alrededor de mil millones de operaciones por segundo).
Si usamos una estructura simple llamada tabla hash (una tabla de búsqueda de velocidad instantánea, también conocida como mapa hash o diccionario), pagamos un pequeño costo al preprocesar todo en O(N) . A partir de entonces, solo toma un tiempo constante en promedio para buscar algo por su clave (en este caso, nuestra clave son las coordenadas de latitud y longitud, redondeadas en una cuadrícula; buscamos los espacios de cuadrícula adyacentes de los cuales solo hay 9, que es un constante).
Nuestra tarea pasó de una O(N²) inviable a una O(N) manejable, y todo lo que tuvimos que hacer fue pagar un costo menor para hacer una tabla hash.
analogía : la analogía en este caso particular es un rompecabezas: creamos una estructura de datos que explota alguna propiedad de los datos. Si nuestros segmentos de camino son como piezas de rompecabezas, los agrupamos por color y patrón. Luego explotamos esto para evitar realizar trabajos adicionales más adelante (comparando piezas de rompecabezas de colores similares entre sí, no con cada otra pieza de rompecabezas).

La moraleja de la historia: una estructura de datos nos permite acelerar las operaciones. Incluso las estructuras de datos más avanzadas pueden permitirle combinar, retrasar o incluso ignorar las operaciones de manera increíblemente inteligente. Diferentes problemas tendrían diferentes analogías, pero todos implicarían organizar los datos de una manera que explote alguna estructura que nos importa, o que le hemos impuesto artificialmente para la contabilidad. Trabajamos antes de tiempo (básicamente planificación y organización), ¡y ahora las tareas repetidas son mucho más fáciles!

Ejemplo práctico: visualizar órdenes de crecimiento mientras se codifica.

La notación asintótica es, en esencia, bastante separada de la programación. La notación asintótica es un marco matemático para pensar cómo se escalan las cosas, y se puede utilizar en muchos campos diferentes. Dicho esto ... así es como se aplica la notación asintótica a la codificación.

Lo básico: cuando interactuamos con cada elemento de una colección de tamaño A (como una matriz, un conjunto, todas las claves de un mapa, etc.), o realizamos iteraciones de un bucle, es un factor multiplicativo del tamaño A ¿Por qué digo "un factor multiplicativo"? - porque los bucles y las funciones (casi por definición) tienen un tiempo de ejecución multiplicativo: el número de iteraciones, los tiempos de trabajo realizados en el bucle (o para las funciones: el número de veces que llama al Función, tiempos de trabajo realizados en la función). (Esto es válido si no hacemos nada sofisticado, como saltar bucles o salir temprano del bucle, o cambiar el flujo de control en la función basada en argumentos, lo cual es muy común). Aquí hay algunos ejemplos de técnicas de visualización, con un pseudocódigo adjunto.

(aquí, las x s representan unidades de trabajo de tiempo constante, instrucciones del procesador, códigos de operación del intérprete, lo que sea)

for(i=0; i<A; i++) // A x ... some O(1) operation // 1 --> A*1 --> O(A) time visualization: |<------ A ------->| 1 2 3 4 5 x x ... x other languages, multiplying orders of growth: javascript, O(A) time and space someListOfSizeA.map((x,i) => [x,i]) python, O(rows*cols) time and space [[r*c for c in range(cols)] for r in range(rows)]

Ejemplo 2:

for every x in listOfSizeA: // A x ... some O(1) operation // 1 some O(B) operation // B for every y in listOfSizeC: // C x ... some O(1) operation // 1 --> O(A*(1 + B + C)) O(A*(B+C)) (1 is dwarfed) visualization: |<------ A ------->| 1 x x x x x x ... x 2 x x x x x x ... x ^ 3 x x x x x x ... x | 4 x x x x x x ... x | 5 x x x x x x ... x B <-- A*B x x x x x x x ... x | ................... | x x x x x x x ... x v x x x x x x x ... x ^ x x x x x x x ... x | x x x x x x x ... x | x x x x x x x ... x C <-- A*C x x x x x x x ... x | ................... | x x x x x x x ... x v

Ejemplo 3:

function nSquaredFunction(n) { total = 0 for i in 1..n: // N x for j in 1..n: // N x total += i*k // 1 return total } // O(n^2) function nCubedFunction(a) { for i in 1..n: // A x print(nSquaredFunction(a)) // A^2 } // O(a^3)

Si hacemos algo un poco complicado, es posible que aún puedas imaginar visualmente lo que está sucediendo:

Aquí, lo más importante es el contorno reconocible más pequeño que puede dibujar; un triángulo es una forma bidimensional (0.5 A ^ 2), así como un cuadrado es una forma bidimensional (A ^ 2); el factor constante de dos aquí permanece en la relación asintótica entre los dos, sin embargo, lo ignoramos como todos los factores ... (Hay algunos matices desafortunados en esta técnica en los que no entro aquí; puede confundirlo).

Por supuesto, esto no significa que los bucles y las funciones sean malos; por el contrario, son los componentes básicos de los lenguajes de programación modernos, y nos encantan. Sin embargo, podemos ver que la forma en que tejemos los bucles, las funciones y las condiciones junto con nuestros datos (flujo de control, etc.) imita el uso del espacio y el tiempo de nuestro programa. Si el uso del tiempo y el espacio se convierte en un problema, es cuando recurrimos a la inteligencia y encontramos un algoritmo o una estructura de datos sencillos que no habíamos considerado para reducir el orden de crecimiento de alguna manera. Sin embargo, estas técnicas de visualización (aunque no siempre funcionan) pueden darle una idea ingenua del peor momento de ejecución.

Aquí hay otra cosa que podemos reconocer visualmente:

<----------------------------- N -----------------------------> x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x

Podemos simplemente reorganizar esto y ver que es O (N):

<----------------------------- N -----------------------------> x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

O tal vez logre el paso (N) de los datos, para O (N * log (N)) tiempo total:

<----------------------------- N -----------------------------> ^ x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x | x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x | x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x v x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Sin relación, pero vale la pena volver a mencionarlo: si realizamos un hash (por ejemplo, un diccionario / búsqueda de tabla de hash), ese es un factor de O (1). Eso es bastante rápido.

[myDictionary.has(x) for x in listOfSizeA] /----- O(1) ------/ --> A*1 --> O(A)

Si hacemos algo muy complicado, como con una función recursiva o un algoritmo de dividir y conquistar, ~~puedes usar el Teorema Maestro (generalmente funciona), o en casos ridículos el Teorema de Akra-Bazzi (casi siempre funciona)~~ . tiempo de ejecución de su algoritmo en Wikipedia.

Pero, los programadores no piensan así porque, eventualmente, la intuición del algoritmo se convierte en una segunda naturaleza. Comenzará a codificar algo ineficiente e inmediatamente pensará "¿Estoy haciendo algo sumamente ineficaz? ". Si la respuesta es "sí" Y prevén que realmente importa, entonces puede dar un paso atrás y pensar en varios trucos para hacer que las cosas funcionen más rápido (la respuesta es casi siempre "usar una tabla hash", rara vez "usar un árbol", y muy raramente algo un poco más complicado).

Complejidad amortizada y media.

También existe el concepto de "amortizado" y / o "caso promedio" (tenga en cuenta que estos son diferentes).

Caso promedio : esto no es más que el uso de la notación O grande para el valor esperado de una función, en lugar de la función en sí. En el caso habitual en el que considera que todas las entradas son igualmente probables, el caso promedio es solo el promedio del tiempo de ejecución. Por ejemplo, con quicksort, aunque el peor de los casos es O(N^2) para algunas entradas realmente malas, el caso promedio es el O(N log(N)) habitual O(N log(N)) (las entradas realmente malas son muy pequeñas en número, por lo que Pocos que no los notamos en el caso medio).

El peor caso amortizado : algunas estructuras de datos pueden tener una complejidad del peor de los casos que es grande, pero garantiza que si realiza muchas de estas operaciones, la cantidad promedio de trabajo que realice será mejor que el peor de los casos. Por ejemplo, puede tener una estructura de datos que normalmente toma tiempo O(1) constante.Sin embargo, de vez en cuando tendrá ''hipo'' y tomará O(N)tiempo para una operación aleatoria, porque tal vez necesite hacer alguna contabilidad o recolección de basura o algo ... pero le promete que si tiene un hipo, no volverá a tener hipo por N Más operaciones. El costo en el peor de los casos sigue siendo O(N)por operación, pero el costo amortizado en muchas corridas es O(N)/N= O(1)por operación. Debido a que las grandes operaciones son lo suficientemente raras, se puede considerar que la gran cantidad de trabajo ocasional se mezcla con el resto del trabajo como un factor constante. Decimos que el trabajo se "amortiza" en un número suficientemente grande de llamadas que desaparece de manera asintótica.

La analogía para el análisis amortizado:
Conduces un coche. Ocasionalmente, debe pasar 10 minutos yendo a la estación de servicio y luego pasar 1 minuto rellenando el tanque con gasolina. Si hiciera esto cada vez que fuera a algún lugar con su automóvil (pase 10 minutos conduciendo a la estación de servicio, pase unos segundos llenando una fracción de galón), sería muy ineficiente. Pero si llena el tanque una vez cada pocos días, los 11 minutos que lleva conduciendo a la estación de servicio se "amortizan" en un número suficientemente grande de viajes, que puede ignorarlo y pretender que todos sus viajes fueron un 5% más largos.

Comparación entre caso promedio y caso peor amortizado:

Caso medio: hacemos algunas suposiciones acerca de nuestros aportes; es decir, si nuestras entradas tienen diferentes probabilidades, entonces nuestros resultados / tiempos de ejecución tendrán diferentes probabilidades (de las cuales tomamos el promedio). Por lo general, asumimos que todas nuestras entradas son igualmente probables (probabilidad uniforme), pero si las entradas del mundo real no se ajustan a nuestros supuestos de "entrada promedio", los cálculos de salida / tiempo de ejecución promedio pueden carecer de sentido. Sin embargo, si anticipa entradas aleatorias uniformes, ¡es útil pensar en ello!
El peor de los casos amortizado: si utiliza una estructura de datos del peor de los casos amortizada, se garantiza que el rendimiento se encuentra dentro del peor de los casos amortizado ... eventualmente (incluso si las entradas son elegidas por un demonio malvado que sabe todo y está intentando atornillarlo encima). Por lo general, usamos esto para analizar algoritmos que pueden ser muy "entrecortados" en el rendimiento con grandes contratiempos inesperados, pero con el tiempo se desempeñan tan bien como otros algoritmos. (Sin embargo, a menos que su estructura de datos tenga límites superiores para mucho trabajo sobresaliente que esté dispuesto a postergar, un atacante malvado podría quizás forzarlo a ponerse al día con la cantidad máxima de trabajo postergado de una vez.

Sin embargo, si está razonablemente preocupado por un atacante, hay muchos otros vectores de ataque algorítmico de los que preocuparse además de la amortización y el caso promedio.

Tanto el caso promedio como la amortización son herramientas increíblemente útiles para pensar y diseñar con la escala en mente.

(Consulte la diferencia entre el análisis de caso promedio y amortizado si está interesado en este subtema).

Big-O multidimensional

La mayoría de las veces, las personas no se dan cuenta de que hay más de una variable en el trabajo. Por ejemplo, en un algoritmo de búsqueda de cadenas, su algoritmo puede tomar tiempo O([length of text] + [length of query]), es decir, es lineal en dos variables como O(N+M). Otros algoritmos más ingenuos pueden ser O([length of text]*[length of query])o O(N*M). Ignorar múltiples variables es uno de los descuidos más comunes que veo en el análisis de algoritmos y puede perjudicarlo al diseñar un algoritmo.

La historia completa

Tenga en cuenta que la gran O no es toda la historia. Puede acelerar drásticamente algunos algoritmos mediante el uso de almacenamiento en caché, por lo que la memoria caché-ajeno, evitando los cuellos de botella mediante la colaboración con la memoria RAM en lugar de disco, usando la paralelización, o hacer el trabajo antes de tiempo - estas técnicas son a menudo independiente del crecimiento de orden de Notación "O grande", aunque a menudo verá la cantidad de núcleos en la notación O grande de algoritmos paralelos.

También tenga en cuenta que debido a las restricciones ocultas de su programa, es posible que no le importe el comportamiento asintótico. Puede estar trabajando con un número limitado de valores, por ejemplo:

Si está clasificando algo así como 5 elementos, no desea utilizar el O(N log(N))quicksort rápido ; desea utilizar la ordenación por inserción, que funciona bien en entradas pequeñas. Estas situaciones a menudo aparecen en algoritmos de dividir y conquistar, donde se divide el problema en subproblemas cada vez más pequeños, como la clasificación recursiva, las transformadas rápidas de Fourier o la multiplicación de matrices.
Si algunos valores están limitados de manera efectiva debido a algún hecho oculto (por ejemplo, el nombre humano promedio se limita suavemente a unas 40 letras, y la edad humana se limita suavemente a alrededor de 150). También puede imponer límites a su entrada para hacer que los términos sean constantes.

En la práctica, incluso entre los algoritmos que tienen el mismo rendimiento asintótico o similar, su mérito relativo en realidad puede estar impulsado por otras cosas, como: otros factores de rendimiento (quicksort y mergesort son ambos O(N log(N)), pero quicksort aprovecha las cachés de CPU); consideraciones de incumplimiento, como la facilidad de implementación; si una biblioteca está disponible, y qué tan reputada y mantenida es la biblioteca.

Los programas también se ejecutarán más lentamente en una computadora de 500 MHz frente a una computadora de 2 GHz. Realmente no consideramos esto como parte de los límites de recursos, porque pensamos en la escala en términos de recursos de la máquina (por ejemplo, por ciclo de reloj), no por segundo real. Sin embargo, hay cosas similares que pueden "secretamente" afectar el rendimiento, como si está ejecutando bajo emulación, o si el compilador optimizó el código o no. Esto puede hacer que algunas operaciones básicas tomen más tiempo (incluso en relación con las demás), o incluso acelerar o ralentizar algunas operaciones de forma asintótica (incluso en relación con las demás). El efecto puede ser pequeño o grande entre diferentes implementaciones y / o entornos. ¿Cambia idiomas o máquinas para realizar ese pequeño trabajo extra? Eso depende de otras cien razones (necesidad, habilidades, compañeros de trabajo, productividad del programador,el valor monetario de su tiempo, familiaridad, soluciones, ¿por qué no ensamblaje o GPU, etc ...), que puede ser más importante que el rendimiento.

Los problemas anteriores, como el lenguaje de programación, casi nunca se consideran parte del factor constante (ni deberían serlo); sin embargo, uno debe ser consciente de ellos, porque a veces (aunque raramente) pueden afectar las cosas. Por ejemplo, en cpython, la implementación de la cola de prioridad nativa es asintóticamente no óptima (en O(log(N))lugar de O(1)para su elección de inserción o búsqueda-min); ¿Usas otra implementación? Probablemente no, ya que la implementación de C es probablemente más rápida y probablemente haya otros problemas similares en otros lugares. Hay compensaciones; A veces importan y otras no.

( Editar : la explicación de "inglés simple" termina aquí.)

Addenda de matemáticas

Para completar, la definición precisa de notación big-O es la siguiente: f(x) ∈ O(g(x))significa que "f es asintóticamente delimitada por const * g": ignorando todo lo que está debajo de algún valor finito de x, existe una constante tal que|f(x)| ≤ const * |g(x)| . (Los otros símbolos son los siguientes: igual que Osignifica ≤, Ωsignifica ≥. Hay variantes en minúsculas: osignifica <y ωsignifica>.) f(x) ∈ Ɵ(g(x))Significa ambos f(x) ∈ O(g(x))y f(x) ∈ Ω(g(x))(delimitado por g): existen algunas constantes tales que f Siempre estará en la "banda" entre const1*g(x)y const2*g(x). Es la afirmación asintótica más fuerte que puede hacer y aproximadamente equivalente ==. (Lo siento, elegí retrasar la mención de los símbolos de valor absoluto hasta ahora, por el bien de la claridad; sobre todo porque nunca he visto aparecer valores negativos en un contexto informático).

La gente usará a menudo = O(...), que es quizás la notación más correcta de ''comp-sci'', y es completamente legítima de usar ... pero uno debe darse cuenta de =que no se está utilizando como igualdad; es una notación compuesta que debe leerse como un idioma. Me enseñaron a usar los más rigurosos ∈ O(...). ∈significa "es un elemento de". O(N²)es en realidad una clase de equivalencia , es decir, es un conjunto de cosas que consideramos iguales. En este caso particular, O(N²)contiene elementos como { 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} y es infinitamente grande, pero aún así es un conjunto. los=la notación podría ser la más común, e incluso se usa en documentos de científicos informáticos de renombre mundial. Además, a menudo es el caso que en un ambiente informal, la gente dirá O(...)cuando quiere decir Ɵ(...); Esto es técnicamente cierto ya que el conjunto de cosas Ɵ(exactlyThis)es un subconjunto de O(noGreaterThanThis)... y es más fácil de escribir. ;-)

Muestra cómo se escala un algoritmo.

O (n ² ) : conocido como complejidad cuadrática.

1 artículo: 1 segundo
10 artículos: 100 segundos
100 artículos: 10000 segundos

Observe que el número de elementos aumenta en un factor de 10, pero el tiempo aumenta en un factor de 10 ² . Básicamente, n = 10 y O (n ² ) nos da el factor de escala n ² que es 10 ² .

O (n) : conocido como complejidad lineal.

1 artículo: 1 segundo
10 artículos: 10 segundos
100 artículos: 100 segundos

Esta vez el número de elementos aumenta en un factor de 10, y también lo hace el tiempo. n = 10 y, por lo tanto, el factor de escala de O (n) es 10.

O (1) : conocido como complejidad constante

1 artículo: 1 segundo
10 artículos: 1 segundo
100 artículos: 1 segundo

El número de elementos sigue aumentando en un factor de 10, pero el factor de escala de O (1) siempre es 1.

O (log n) : conocido como complejidad logarítmica

1 artículo: 1 segundo
10 artículos: 2 segundos
100 artículos: 3 segundos
1000 artículos: 4 segundos
10000 artículos: 5 segundos

El número de cálculos solo se incrementa mediante un registro del valor de entrada. Entonces, en este caso, asumiendo que cada cálculo toma 1 segundo, el registro de la entrada n es el tiempo requerido, por lo tanto, el log n .

Eso es lo esencial. Reducen los cálculos matemáticos por lo que podría no ser exactamente n ² o lo que sea que digan, pero ese será el factor dominante en la escala.

Nota rápida, esto es casi seguro que confunde la notación Big O (que es un límite superior) con la notación Theta (que es un límite de dos lados). En mi experiencia, esto es realmente típico de discusiones en entornos no académicos. Disculpas por cualquier confusión causada.

La complejidad de la gran O se puede visualizar con este gráfico:

La definición más simple que puedo dar para la notación Big-O es esta:

La notación Big-O es una representación relativa de la complejidad de un algoritmo.

Hay algunas palabras importantes y deliberadamente elegidas en esa oración:

relativo: solo puedes comparar manzanas con manzanas. No se puede comparar un algoritmo para hacer una multiplicación aritmética a un algoritmo que ordena una lista de enteros. Pero una comparación de dos algoritmos para realizar operaciones aritméticas (una multiplicación, una adición) le dirá algo significativo;
Representación: Big-O (en su forma más simple) reduce la comparación entre algoritmos a una sola variable. Esa variable se elige en base a observaciones o suposiciones. Por ejemplo, los algoritmos de clasificación generalmente se comparan según las operaciones de comparación (comparando dos nodos para determinar su orden relativo). Esto supone que la comparación es cara. Pero, ¿qué pasa si la comparación es barata pero el intercambio es costoso? Cambia la comparación; y
complejidad: si me toma un segundo ordenar 10.000 elementos, ¿cuánto tiempo me llevará ordenar un millón? La complejidad en este caso es una medida relativa a otra cosa.

Vuelve y vuelve a leer lo anterior cuando hayas leído el resto.

El mejor ejemplo de Big-O que se me ocurre es hacer aritmética. Tome dos números (123456 y 789012). Las operaciones aritméticas básicas que aprendimos en la escuela fueron:

adición;
sustracción;
multiplicación; y
división.

Cada uno de estos es una operación o un problema. Un método para resolver estos se llama un algoritmo .

La adición es la más simple. Alinea los números (a la derecha) y suma los dígitos en una columna que escribe el último número de esa suma en el resultado. La parte de ''diez'' de ese número se traslada a la siguiente columna.

Supongamos que la suma de estos números es la operación más costosa en este algoritmo. Es lógico pensar que para sumar estos dos números juntos debemos sumar 6 dígitos (y posiblemente llevar un 7º). Si sumamos dos números de 100 dígitos, tenemos que hacer 100 adiciones. Si sumamos dos números de 10,000 dígitos tenemos que hacer 10,000 adiciones.

¿Ves el patrón? La complejidad (siendo el número de operaciones) es directamente proporcional al número de dígitos n en el número más grande. A esto lo llamamos O (n) o complejidad lineal .

La resta es similar (excepto que es posible que tenga que pedir prestado en lugar de llevarlo).

La multiplicación es diferente. Alinear los números, tomar el primer dígito en el número inferior y multiplicarlo a su vez por cada dígito en el número superior y así sucesivamente a través de cada dígito. Entonces para multiplicar nuestros dos números de 6 dígitos debemos hacer 36 multiplicaciones. Es posible que tengamos que hacer hasta 10 u 11 columnas para obtener el resultado final también.

Si tenemos dos números de 100 dígitos, necesitamos hacer 10,000 multiplicaciones y 200 sumas. Para dos números de un millón de dígitos necesitamos hacer un trillón (10 ¹² ) multiplicaciones y dos millones de sumas.

A medida que el algoritmo se escala con n cuadrado , esto es O (n ² ) o complejidad cuadrática . Este es un buen momento para introducir otro concepto importante:

Solo nos importa la parte más significativa de la complejidad.

El astuto puede haberse dado cuenta de que podríamos expresar el número de operaciones como: n ² + 2n. Pero como vio en nuestro ejemplo con dos números de un millón de dígitos cada uno, el segundo término (2n) se vuelve insignificante (representando el 0,0002% del total de operaciones en esa etapa).

Uno puede notar que hemos asumido el peor escenario aquí. Mientras multiplicas números de 6 dígitos si uno de ellos es de 4 dígitos y el otro de 6 dígitos, entonces solo tenemos 24 multiplicaciones. Aún así, calculamos el peor de los casos para esa ''n'', es decir, cuando ambos son números de 6 dígitos. Por lo tanto, la notación Big-O es sobre el peor escenario de un algoritmo

La libreta de teléfonos

El siguiente mejor ejemplo que se me ocurre es la guía telefónica, normalmente llamada Páginas Blancas o similar, pero variará de un país a otro. Pero estoy hablando de la que enumera personas por apellido y luego iniciales o primer nombre, posiblemente dirección y luego números de teléfono.

Ahora, si estuviera ordenando a una computadora que busque el número de teléfono de "John Smith" en una guía telefónica que contenga 1,000,000 de nombres, ¿qué haría? Ignorando el hecho de que podrías adivinar qué tan lejos empezaron las S (supongamos que no puedes), ¿qué harías?

Una implementación típica podría ser abrirse al medio, tomar la 500,000 y compararla con "Smith". Si sucede que es "Smith, John", tenemos mucha suerte. Mucho más probable es que "John Smith" sea antes o después de ese nombre. Si es después, dividimos la última mitad de la guía telefónica por la mitad y la repetimos. Si es antes de eso, dividimos la primera mitad de la guía telefónica por la mitad y repetimos. Y así.

Esto se denomina búsqueda binaria y se usa todos los días en la programación, ya sea que se dé cuenta o no.

Entonces, si desea encontrar un nombre en una guía telefónica de un millón de nombres, puede encontrar cualquier nombre haciendo esto como máximo 20 veces. Al comparar los algoritmos de búsqueda, decidimos que esta comparación es nuestra ''n''.

Para una guía telefónica de 3 nombres se necesitan 2 comparaciones (como máximo).
Para 7 lleva como máximo 3.
Para 15 se necesitan 4.
...
Para 1,000,000 se necesitan 20.

Eso es asombrosamente bueno, ¿no?

En términos de Big-O, esto es O (log n) o complejidad logarítmica . Ahora el logaritmo en cuestión podría ser ln (base e), log ₁₀ , log ₂ o alguna otra base. No importa, sigue siendo O (log n), al igual que O (2n ² ) y O (100n ² ) siguen siendo O (n ² ).

En este punto, vale la pena explicar que se puede usar Big O para determinar tres casos con un algoritmo:

Mejor caso: en la búsqueda de la guía telefónica, el mejor caso es que encontramos el nombre en una comparación. Esto es O (1) o complejidad constante ;
Caso esperado: Como se mencionó anteriormente, esto es O (log n); y
Peor caso: Esto también es O (log n).

Normalmente no nos importa el mejor caso. Estamos interesados en el peor y esperado caso. A veces uno u otro de estos serán más importantes.

Volver a la guía telefónica.

¿Qué pasa si tienes un número de teléfono y quieres encontrar un nombre? La policía tiene una guía telefónica inversa, pero tales búsquedas son denegadas al público en general. ¿O son? Técnicamente, puede revertir la búsqueda de un número en una guía telefónica normal. ¿Cómo?

Comienzas en el primer nombre y comparas el número. Si es una coincidencia, genial, si no, pasas a la siguiente. Tienes que hacerlo de esta manera porque la guía telefónica no está ordenada (de todos modos, por número de teléfono).

Entonces, para encontrar un nombre dado el número de teléfono (búsqueda inversa):

Mejor caso: O (1);
Caso esperado: O (n) (para 500,000); y
El peor caso: O (n) (por 1,000,000).

El vendedor ambulante

Este es un problema bastante famoso en informática y merece una mención. En este problema tienes N pueblos. Cada una de esas ciudades está vinculada a una o más ciudades por una carretera de cierta distancia. El problema del vendedor ambulante es encontrar el recorrido más corto que visita cada ciudad.

Suena simple? Piensa otra vez.

Si tienes 3 ciudades A, B y C con carreteras entre todos los pares, entonces podrías ir:

A → B → C
A → C → B
B → C → A
B → A → C
C → A → B
C → B → A

Bueno, en realidad hay menos que eso porque algunos de ellos son equivalentes (A → B → C y C → B → A son equivalentes, por ejemplo, porque usan las mismas carreteras, solo en sentido inverso).

En la actualidad hay 3 posibilidades.

Lleva esto a 4 ciudades y tienes (iirc) 12 posibilidades.
Con 5 es 60.
6 se convierte en 360.

Esta es una función de una operación matemática llamada factorial . Básicamente:

5! = 5 × 4 × 3 × 2 × 1 = 120
6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
...
25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
...
50! = 50 × 49 × ... × 2 × 1 = 3.04140932 × 10 ⁶⁴

Por lo tanto, el problema de Big-O del vendedor ambulante es O (n!) O complejidad factorial o combinatoria .

Para cuando llegas a 200 ciudades, no queda suficiente tiempo en el universo para resolver el problema con las computadoras tradicionales.

Algo sobre lo que pensar.

Tiempo polinomial

Otro punto que quería mencionar rápidamente es que cualquier algoritmo que tenga una complejidad de O (n ^a ) se dice que tiene complejidad polinómica o que se puede resolver en el tiempo polinomial .

O (n), O (n ² ) etc. son todos polinomios. Algunos problemas no pueden resolverse en tiempo polinomial. Ciertas cosas se usan en el mundo debido a esto. La criptografía de clave pública es un buen ejemplo. Es computacionalmente difícil encontrar dos factores primos de un número muy grande. Si no fuera así, no podríamos usar los sistemas de clave pública que usamos.

De todos modos, eso es todo por mi explicación (con suerte, en inglés sencillo) de Big O (revisada).

Definición: - La notación Big O es una notación que dice cómo se realizará el rendimiento de un algoritmo si la entrada de datos aumenta.

Cuando hablamos de algoritmos, hay 3 pilares importantes Entrada, Salida y Procesamiento del algoritmo. La O grande es una notación simbólica que dice si la entrada de datos se incrementa a qué velocidad variará el rendimiento del procesamiento del algoritmo.

Le animo a que vea este video de youtube que explica en profundidad la notación de Big O con ejemplos de código.

Entonces, por ejemplo, supongamos que un algoritmo toma 5 registros y el tiempo requerido para procesarlo es de 27 segundos. Ahora, si aumentamos los registros a 10, el algoritmo toma 105 segundos.

En palabras simples, el tiempo empleado es el cuadrado del número de registros. Podemos denotar esto por O (n ^ 2) . Esta representación simbólica se denomina notación Big O.

Ahora tenga en cuenta que las unidades pueden ser cualquier cosa en las entradas, bytes, número de registros, el rendimiento se puede medir en cualquier unidad, como segundos, minutos, días, etc. Así que no es la unidad exacta sino la relación.

Por ejemplo, mire la siguiente función "Función1" que toma una colección y realiza el procesamiento en el primer registro. Ahora para esta función, el rendimiento será el mismo, independientemente de que pones 1000, 10000 o 100000 registros. Así que podemos denotarlo por O (1) .

void Function1(List<string> data) { string str = data[0]; }

Ahora vea la siguiente función "Function2 ()". En este caso, el tiempo de procesamiento aumentará con el número de registros. Podemos denotar el rendimiento de este algoritmo usando O (n) .

void Function2(List<string> data) { foreach(string str in data) { if (str == "shiv") { return; } } }

Cuando vemos una notación Big O para cualquier algoritmo, podemos clasificarlos en tres categorías de rendimiento:

Categoría de registro y constante: a cualquier desarrollador le encantaría ver el rendimiento de su algoritmo en esta categoría.
Lineal: - El desarrollador no querrá ver algoritmos en esta categoría, hasta que sea la última opción o la única opción que queda.
Exponencial: - Aquí es donde no queremos ver nuestros algoritmos y es necesario volver a trabajar.

Entonces, al observar la notación Big O, categorizamos las zonas buenas y malas para los algoritmos.

Te recomendaría que veas este video de 10 minutos que discute Big O con un código de muestra

https://www.youtube.com/watch?v=k6kxtzICG_g

Big O describe la naturaleza de escala fundamental de un algoritmo.

Hay mucha información que Big O no le dice acerca de un algoritmo dado. Corta al hueso y solo proporciona información acerca de la naturaleza de escala de un algoritmo, específicamente cómo se escala el uso del recurso (tiempo de reflexión o memoria) de un algoritmo en respuesta al "tamaño de entrada".

Considera la diferencia entre una máquina de vapor y un cohete. No son simplemente diferentes variedades de la misma cosa (como, por ejemplo, un motor Prius versus un motor Lamborghini) sino que son sistemas de propulsión dramáticamente diferentes, en su núcleo. Un motor de vapor puede ser más rápido que un cohete de juguete, pero ningún motor de pistón de vapor podrá alcanzar las velocidades de un vehículo de lanzamiento orbital. Esto se debe a que estos sistemas tienen diferentes características de escalamiento con respecto a la relación del combustible requerido ("uso de recursos") para alcanzar una velocidad determinada ("tamaño de entrada").

¿Por qué es esto tan importante? Debido a que el software se ocupa de problemas que pueden diferir en tamaño por factores de hasta un billón. Considera eso por un momento. La relación entre la velocidad necesaria para viajar a la Luna y la velocidad de la marcha humana es inferior a 10,000: 1, y es absolutamente pequeña en comparación con el rango de tamaños de entrada que el software puede enfrentar. Y debido a que el software puede enfrentar un rango astronómico en el tamaño de entrada, existe la posibilidad de que la complejidad de un algoritmo de Big O, es una naturaleza de escala fundamental, para superar cualquier detalle de implementación.

Considere el ejemplo de clasificación canónica. La ordenación por burbuja es O (n ² ), mientras que la ordenación por fusión es O (n log n). Supongamos que tiene dos aplicaciones de clasificación, la aplicación A que utiliza la clasificación de burbujas y la aplicación B que utiliza la combinación de clasificación, y digamos que para tamaños de entrada de alrededor de 30 elementos, la aplicación A es 1.000 veces más rápida que la aplicación B en la clasificación. Si nunca tiene que ordenar más de 30 elementos, es obvio que debería preferir la aplicación A, ya que es mucho más rápido en estos tamaños de entrada. Sin embargo, si encuentra que puede tener que ordenar diez millones de elementos, entonces lo que esperaría es que la aplicación B en realidad sea miles de veces más rápida que la aplicación A en este caso, debido en su totalidad a la forma en que se ajusta cada algoritmo.

Ejemplo de algoritmo (Java):

// given a list of integers L, and an integer K public boolean simple_search(List<Integer> L, Integer K) { // for each integer i in list L for (Integer i : L) { // if i is equal to K if (i == K) { return true; } } return false; }

Descripción del algoritmo:

Este algoritmo busca una lista, elemento por elemento, buscando una clave,
Iterando en cada elemento de la lista, si es la clave, devuelva Verdadero,
Si el bucle ha terminado sin encontrar la clave, devuelva False.

La notación Big-O representa el límite superior de la complejidad (tiempo, espacio, ...)

Para encontrar el Big-O en la complejidad del tiempo:

Calcule cuánto tiempo (en relación con el tamaño de entrada) lleva el peor de los casos:
El peor de los casos: la clave no existe en la lista.
Tiempo (el peor de los casos) = 4n + 1
Tiempo: O (4n + 1) = O (n) | en Big-O, las constantes son descuidadas
O (n) ~ Lineal

También hay Big-Omega, que representan la complejidad del Mejor Caso:

Best-Case: la clave es el primer elemento.
Tiempo (mejor caso) = 4
Tiempo: Ω (4) = O (1) ~ Instant / Constant

Gran o

f (x) = O ( g (x)) cuando x va a a (por ejemplo, a = + ∞) significa que hay una función k tal que:

f (x) = k (x) g (x)
k está delimitado en alguna vecindad de a (si a = + ∞, esto significa que hay números N y M, por lo que para cada x> N, | k (x) | <M).

En otras palabras, en inglés simple: f (x) = O ( g (x)), x → a, significa que en una vecindad de a, f se descompone en el producto de g y alguna función limitada.

Pequeño o

Por cierto, aquí está para comparación la definición de pequeño o.

f (x) = o ( g (x)) cuando x va a un medio que hay una función k tal que:

f (x) = k (x) g (x)
k (x) va a 0 cuando x va a a.

Ejemplos

sen x = O (x) cuando x → 0.
sen x = O (1) cuando x → + ∞,
x ² + x = O (x) cuando x → 0,
x ² + x = O (x ² ) cuando x → + ∞,
ln (x) = o (x) = O (x) cuando x → + ∞.

¡Atención! La notación con el signo igual "=" usa una "igualdad falsa": es cierto que o (g (x)) = O (g (x)), pero falso que O (g (x)) = o (g (X)). De manera similar, está bien escribir "ln (x) = o (x) cuando x → + ∞", pero la fórmula "o (x) = ln (x)" no tendría sentido.

Más ejemplos

O (1) = O (n) = O (n ² ) cuando n → + ∞ (pero no al revés, la igualdad es "falsa"),
O (n) + O (n ² ) = O (n ² ) cuando n → + ∞
O (O (n ² )) = O (n ² ) cuando n → + ∞
O (n ² ) O (n ³ ) = O (n ⁵ ) cuando n → + ∞

Aquí está el artículo de Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

La forma más simple de verlo (en inglés simple)

Estamos tratando de ver cómo el número de parámetros de entrada afecta el tiempo de ejecución de un algoritmo. Si el tiempo de ejecución de su aplicación es proporcional al número de parámetros de entrada, entonces se dice que está en Big O de n.

La declaración anterior es un buen comienzo pero no es completamente cierta.

Una explicación más precisa (matemática).

Suponer

n = número de parámetros de entrada

T (n) = La función real que expresa el tiempo de ejecución del algoritmo como una función de n

c = una constante

f (n) = Una función aproximada que expresa el tiempo de ejecución del algoritmo como una función de n

Entonces, en lo que se refiere a Big O, la aproximación f (n) se considera suficientemente buena siempre que la siguiente condición sea verdadera.

lim T(n) ≤ c×f(n) n→∞

La ecuación se lee cuando As n se aproxima al infinito, T de n, es menor o igual que c veces f de n.

En gran notación O esto está escrito como

T(n)∈O(n)

Esto se lee como T de n está en gran O de n.

Volver al ingles

De acuerdo con la definición matemática anterior, si dice que su algoritmo es una O grande de n, significa que es una función de n (número de parámetros de entrada) o más rápido . Si su algoritmo es Gran O de n, entonces también es automáticamente el Gran O de n cuadrado.

Big O of n significa que mi algoritmo se ejecuta al menos tan rápido como este. No puedes mirar la notación Big O de tu algoritmo y decir que es lento. Sólo puedes decir que es rápido.

Mira this para un video tutorial sobre Big O de UC Berkley. Es en realidad un concepto simple. Si escuchas que el profesor Shewchuck (también conocido como maestro a nivel de Dios) lo explica, dirás "¡Eso es todo!".

Aquí está el sencillo bestiario en inglés que tiendo a usar cuando explico las variedades comunes de Big-O

En todos los casos, prefiera los algoritmos más arriba en la lista a los que están más abajo en la lista. Sin embargo, el costo de mudarse a una clase de complejidad más cara varía significativamente.

O (1):

Sin crecimiento. Independientemente de cuán grande sea el problema, puede resolverlo en el mismo período de tiempo. Esto es un tanto análogo a la transmisión, en la que se necesita la misma cantidad de energía para transmitir en una distancia determinada, independientemente del número de personas que se encuentren dentro del rango de transmisión.

O (log n ):

Esta complejidad es la misma que O (1), excepto que es un poco peor. Para todos los propósitos prácticos, puede considerar esto como una escala constante muy grande. La diferencia en el trabajo entre el procesamiento de 1 mil y 1 mil millones de ítems es solo un factor seis.

O ( n ):

El costo de resolver el problema es proporcional al tamaño del problema. Si su problema se duplica en tamaño, entonces el costo de la solución se duplica. Dado que la mayoría de los problemas deben analizarse en la computadora de alguna manera, ya que la entrada de datos, las lecturas de disco o el tráfico de red, generalmente es un factor de escala asequible.

O ( n log n ):

Esta complejidad es muy similar a O ( n ) . Para todos los propósitos prácticos, los dos son equivalentes. Este nivel de complejidad en general todavía sería considerado escalable. Al ajustar los supuestos, algunos algoritmos O ( n log n ) se pueden transformar en algoritmos O ( n ) . Por ejemplo, delimitar el tamaño de las teclas reduce la clasificación de O ( n log n ) a O ( n ) .

O ( n ² ):

Crece como un cuadrado, donde n es la longitud del lado de un cuadrado. Esta es la misma tasa de crecimiento que el "efecto de red", donde todos en una red pueden conocer a todos los demás en la red. El crecimiento es caro. Las soluciones más escalables no pueden usar algoritmos con este nivel de complejidad sin hacer gimnasia significativa. Esto generalmente se aplica a todas las demás complejidades polinomiales - O ( n ^k ) - también.

O (2 ⁿ ):

No se escala. No tienes ninguna esperanza de resolver ningún problema de tamaño no trivial. Útil para saber qué evitar y para que los expertos encuentren algoritmos aproximados que estén en O ( n ^k ) .

Big O describe un límite superior en el comportamiento de crecimiento de una función, por ejemplo, el tiempo de ejecución de un programa, cuando las entradas se vuelven grandes.

Ejemplos:

O (n): si doblo el tamaño de entrada, el tiempo de ejecución se duplica
O (n ² ): si el tamaño de entrada duplica las cuadruplicaciones del tiempo de ejecución
O (log n): si el tamaño de entrada se duplica, el tiempo de ejecución aumenta en uno
O (2 ⁿ ): si el tamaño de entrada aumenta en uno, el tiempo de ejecución se duplica

El tamaño de entrada suele ser el espacio en bits necesario para representar la entrada.

Big O es solo una forma de "Expresarte" de una manera común, "¿Cuánto tiempo / espacio se necesita para ejecutar mi código?".

Con frecuencia puede ver O (n), O (n ² ), O (nlogn), etc., todas estas son solo formas de mostrar; ¿Cómo cambia un algoritmo?

O (n) significa que Big O es n, y ahora puedes pensar, "¿¡Qué es n !?" Pues "n" es la cantidad de elementos. Imágenes que desea buscar un elemento en una matriz. Tendría que mirar cada elemento y como "¿Es usted el elemento / elemento correcto?" en el peor de los casos, el ítem está en el último índice, lo que significa que tomó tanto tiempo como hay ítems en la lista, así que para ser genéricos, decimos "oh hey, n es una cantidad justa de valores dados". .

Entonces, puede que entienda lo que significa "n ² ", pero para ser aún más específico, juegue con el pensamiento de que tiene un algoritmo de clasificación simple, el más simple; ordenamiento de burbuja. Este algoritmo debe mirar a través de la lista completa, para cada elemento.

Mi lista

El flujo aquí sería:

Compara 1 y 6, ¿cuál es el más grande? Ok 6 está en la posición correcta, avanzando!
Compara 6 y 3, ¡oh, 3 es menos! Vamos a mover eso, Ok, la lista ha cambiado, ¡necesitamos comenzar desde el principio ahora!

Esto es O n ² porque, debe mirar todos los elementos de la lista, hay elementos "n". Para cada artículo, miras todos los artículos una vez más, para comparar, esto también es "n", así que para cada artículo, te ves "n" veces que significa n * n = n ²

Espero que esto sea tan simple como lo quieras.

Pero recuerda, Big O es solo una forma de expersarte en la forma de tiempo y espacio.

Big O es una medida de cuánto tiempo / espacio usa un algoritmo en relación con el tamaño de su entrada.

Si un algoritmo es O (n), el tiempo / espacio aumentará a la misma velocidad que su entrada.

Si un algoritmo es O (n ² ), entonces el tiempo / espacio aumenta a la velocidad de su entrada al cuadrado.

y así.

Esta es una explicación muy simplificada, pero espero que cubra los detalles más importantes.

Digamos que su algoritmo que trata el problema depende de algunos ''factores'', por ejemplo, hagamos que sea N y X.

Dependiendo de N y X, su algoritmo requerirá algunas operaciones, por ejemplo, en el caso MÁS PEQUEÑO de sus 3(N^2) + log(X)operaciones.

Como Big-O no se preocupa demasiado por el factor constante (también conocido como 3), el Big-O de su algoritmo sí lo es O(N^2 + log(X)). Básicamente, se traduce "la cantidad de operaciones que su algoritmo necesita para las peores escalas de caso con esto".

La notación Big O es la más comúnmente utilizada por los programadores como una medida aproximada de cuánto tardará en completarse un cálculo (algoritmo) expresado en función del tamaño del conjunto de entrada.

Big O es útil para comparar qué tan bien se escalarán dos algoritmos a medida que aumenta el número de entradas.

Más precisamente, la notación Big O se utiliza para expresar el comportamiento asintótico de una función. Eso significa cómo se comporta la función cuando se aproxima al infinito.

En muchos casos, la "O" de un algoritmo caerá en uno de los siguientes casos:

O (1) : el tiempo para completar es el mismo independientemente del tamaño del conjunto de entrada. Un ejemplo es acceder a un elemento de matriz por índice.
O (Log N) : el tiempo para completar aumenta aproximadamente en línea con el log2 (n). Por ejemplo, 1024 elementos llevan aproximadamente el doble que 32 elementos, porque Log2 (1024) = 10 y Log2 (32) = 5. Un ejemplo es encontrar un elemento en un árbol de búsqueda binario (BST).
O (N) : tiempo para completar esa escala linealmente con el tamaño del conjunto de entrada. En otras palabras, si duplica el número de elementos en el conjunto de entrada, el algoritmo demora aproximadamente el doble. Un ejemplo es contar el número de elementos en una lista vinculada.
O (N Log N) : el tiempo para completar aumenta según el número de elementos multiplicado por el resultado de Log2 (N). Un ejemplo de esto es el ordenamiento dinámico y el ordenamiento rápido .
O (N ^ 2) : el tiempo para completar es aproximadamente igual al cuadrado del número de elementos. Un ejemplo de esto es el tipo burbuja .
O (N!) : El tiempo para completar es el factorial del conjunto de entrada. Un ejemplo de esto es la solución de fuerza bruta del problema del vendedor ambulante .

Big O ignora los factores que no contribuyen de manera significativa a la curva de crecimiento de una función a medida que el tamaño de entrada aumenta hacia el infinito. Esto significa que las constantes que se agregan o se multiplican por la función simplemente se ignoran.

Ok mis 2cents

Big-O, es la tasa de aumento del recurso consumido por programa, wrt problem-instance-size

Recurso: podría ser el tiempo total de CPU, podría ser el máximo espacio de RAM. Por defecto se refiere al tiempo de CPU.

Digamos que el problema es "Encuentra la suma",

int Sum(int*arr,int size){ int sum=0; while(size-->0) sum+=arr[size]; return sum; }

problema-instancia = {5,10,15} ==> problema-instancia-tamaño = 3, iteraciones-en-bucle = 3

problema-instancia = {5,10,15,20,25} ==> problema-instancia-tamaño = 5 iteraciones-en-bucle = 5

Para entradas de tamaño "n", el programa está creciendo a la velocidad de "n" iteraciones en la matriz. Por lo tanto, Big-O es N expresado como O (n)

Di que el problema es "Encuentra la combinación",

void Combination(int*arr,int size) { int outer=size,inner=size; while(outer -->0) { inner=size; while(inner -->0) cout<<arr[outer]<<"-"<<arr[inner]<<endl; } }

problema-instancia = {5,10,15} ==> problema-instancia-tamaño = 3, total de iteraciones = 3 * 3 = 9

problema-instancia = {5,10,15,20,25} ==> problema-instancia-tamaño = 5, total de iteraciones = 5 * 5 = 25

Para entradas de tamaño "n", el programa está creciendo a la velocidad de "n * n" iteraciones en la matriz. Por lo tanto, Big-O es N ² expresado como O (n ² )

Si tiene una noción adecuada de infinito en su cabeza, entonces hay una breve descripción:

La notación Big O le dice el costo de resolver un problema infinitamente grande.

Y además

Los factores constantes son despreciables.

Si actualiza a una computadora que puede ejecutar su algoritmo dos veces más rápido, la notación O grande no lo notará. Las mejoras constantes del factor son demasiado pequeñas como para que se noten en la escala con la que trabaja la gran notación O. Tenga en cuenta que esta es una parte intencional del diseño de la notación O grande.

Aunque se puede detectar cualquier cosa "más grande" que un factor constante, sin embargo.

Cuando esté interesado en realizar cálculos cuyo tamaño sea lo suficientemente "grande" para que se considere aproximadamente infinito, la notación O grande es aproximadamente el costo de resolver su problema.

Si lo anterior no tiene sentido, entonces no tiene una noción intuitiva compatible de infinito en su cabeza, y probablemente debería ignorar todo lo anterior; La única forma que conozco para hacer rigurosas estas ideas, o para explicarlas si no son ya intuitivamente útiles, es enseñarle primero la notación O grande o algo similar. (aunque, una vez que entiendas bien la gran notación O en el futuro, puede valer la pena revisar estas ideas)

Una respuesta simple y sencilla puede ser:

Big O representa el peor tiempo / espacio posible para ese algoritmo. El algoritmo nunca tomará más espacio / tiempo por encima de ese límite. Big O representa la complejidad de tiempo / espacio en el caso extremo.

¿Quieres saber todo lo que hay que saber de la gran O? Yo también.

Así que para hablar de O grande, usaré palabras que solo tienen un latido. Un sonido por palabra. Las pequeñas palabras son rápidas. Tú conoces estas palabras, y yo también. Usaremos palabras con un solo sonido. Ellos son pequeños. ¡Estoy seguro de que sabrás todas las palabras que usaremos!

Ahora, vamos a hablar de trabajo. La mayor parte del tiempo, no me gusta el trabajo. Te gusta el trabajo Puede ser el caso que lo haga, pero estoy seguro de que no lo hago.

No me gusta ir a trabajar. No me gusta pasar el tiempo en el trabajo. Si tuviera mi camino, solo me gustaría jugar y hacer cosas divertidas. ¿Sientes lo mismo que yo?

Ahora, a veces, tengo que ir a trabajar. Es triste pero cierto. Entonces, cuando estoy en el trabajo, tengo una regla: trato de hacer menos trabajo. Tan cerca de no trabajar como pueda. ¡Entonces voy a jugar!

Así que aquí está la gran noticia: ¡la gran O puede ayudarme a no hacer el trabajo! Puedo jugar más tiempo, si conozco una gran O. ¡Menos trabajo, más juego! Eso es lo que O grande me ayuda a hacer.

Ahora tengo algo de trabajo. Tengo esta lista: uno, dos, tres, cuatro, cinco, seis. Debo agregar todas las cosas en esta lista.

Wow, odio el trabajo. Pero bueno, tengo que hacer esto. Así que ahí voy.

Uno más dos son tres ... más tres son seis ... y cuatro es ... No sé. Me perdí. Es demasiado difícil para mí hacerlo en mi cabeza. No me importa mucho este tipo de trabajo.

Así que no hagamos el trabajo. Vamos a ti y a mí, solo pensemos en lo difícil que es. ¿Cuánto trabajo tendría que hacer para sumar seis números?

Bien, veamos. Debo agregar uno y dos, y luego agregarlo a tres, y luego agregarlo a cuatro ... En total, cuento seis sumas. Tengo que hacer seis adiciones para resolver esto.

Aquí viene la gran O, para decirnos qué tan difícil es esta matemática.

Big O dice: debemos hacer seis agregados para resolver esto. Un agregado, para cada cosa del uno al seis. Seis pequeños fragmentos de trabajo ... cada bit de trabajo es un agregado.

Bueno, no haré el trabajo de agregarlos ahora. Pero sé lo difícil que sería. Serían seis añadidos.

Oh no, ahora tengo más trabajo. Sheesh ¿Quién hace este tipo de cosas?

¡Ahora me piden que agregue de uno a diez! ¿Por qué habría de hacer eso? No quería agregar uno a seis. Añadir de uno a diez ... bueno ... ¡sería aún más difícil!

¿Cuánto más difícil sería? ¿Cuánto más trabajo tendría que hacer? ¿Necesito más o menos pasos?

Bueno, supongo que tendría que hacer diez sumas ... una para cada cosa de una a diez. Diez es más que seis. ¡Tendría que trabajar mucho más para agregar de uno a diez, que de uno a seis!

No quiero añadir ahora mismo. Solo quiero pensar en lo difícil que puede ser agregar eso. Y, espero, jugar tan pronto como pueda.

Para agregar de uno a seis, eso es algo de trabajo. ¿Pero ves, para sumar de uno a diez, eso es más trabajo?

Big O es tu amiga y la mía. Big O nos ayuda a pensar cuánto trabajo tenemos que hacer para poder planificar. Y, si somos amigos de la gran O, ¡él puede ayudarnos a elegir un trabajo que no sea tan difícil!

Ahora debemos hacer un nuevo trabajo. Oh no. No me gusta este trabajo en absoluto.

El nuevo trabajo es: agregar todas las cosas de uno a n.

¡Espere! ¿Qué es n? ¿Me perdí eso? ¿Cómo puedo agregar de uno a n si no me dices qué es n?

Bueno, no sé qué es n. No me lo dijeron. Fuiste tu ¿No? Oh bien.Así que no podemos hacer el trabajo. Uf.

Pero aunque no hagamos el trabajo ahora, podemos adivinar cuán difícil sería, si supiéramos n. Tendríamos que sumar n cosas, ¿verdad? ¡Por supuesto!

Ahora viene una gran O, y él nos dirá cuán difícil es este trabajo. Él dice: agregar todas las cosas de uno a N, uno por uno, es O (n). Para agregar todas estas cosas, [Sé que debo agregar n veces.] [1] ¡Eso es grande O! Nos dice lo difícil que es hacer algún tipo de trabajo.

Para mí, pienso en el gran O como un gran jefe lento. Piensa en el trabajo, pero no lo hace. Él podría decir: "Ese trabajo es rápido". O, podría decir, "¡Ese trabajo es tan lento y duro!" Pero él no hace el trabajo. Solo mira el trabajo y luego nos dice cuánto tiempo puede llevar.

Me importa mucho la gran O. ¿Por qué? ¡No me gusta trabajar! A nadie le gusta trabajar. Es por eso que todos amamos a lo grande O! Nos dice que tan rápido podemos trabajar. Nos ayuda a pensar en lo difícil que es el trabajo.

Uh oh, más trabajo. Ahora, no hagamos el trabajo. Pero, vamos a hacer un plan para hacerlo, paso a paso.

Nos dieron una baraja de diez cartas. Todos están mezclados: siete, cuatro, dos, seis ... nada en absoluto. Y ahora ... nuestro trabajo es ordenarlos.

Ergh. ¡Eso suena como un monton de trabajo!

¿Cómo podemos ordenar esta baraja? Tengo un plan.

Observaré cada par de cartas, par por par, a través de la baraja, desde el primero hasta el último. Si la primera carta de un par es grande y la siguiente de ese par es pequeña, las cambio. De lo contrario, voy a la siguiente pareja, y así sucesivamente ... y pronto, la cubierta está lista.

Cuando se termina el mazo, pregunto: ¿cambié las cartas en ese pase? Si es así, debo hacerlo todo una vez más, desde arriba.

En algún momento, en algún momento, no habrá swaps, y nuestro tipo de mazo estará listo. ¡Mucho trabajo!

Bueno, ¿cuánto trabajo sería eso, ordenar las tarjetas con esas reglas?

Tengo diez cartas. Y, la mayoría del tiempo, es decir, si no tengo mucha suerte, debo pasar por todo el mazo hasta diez veces, con hasta diez intercambios de cartas cada vez a través del mazo.

Big O, ayúdame!

Big O entra y dice: para una baraja de n cartas, ordenarlas de esta manera se hará en tiempo O (N cuadrado).

¿Por qué dice n al cuadrado?

Bueno, sabes que n al cuadrado es n veces n. Ahora, lo entiendo: n tarjetas revisadas, hasta lo que podría ser n veces a través de la baraja. Eso es dos bucles, cada uno con n pasos. Eso es n al cuadrado mucho trabajo por hacer. Mucho trabajo, seguro!

Ahora, cuando la O grande dice que tomará O (n al cuadrado) el trabajo, no significa que n al cuadrado agregue, en la nariz. Podría ser un poco menos, para algunos casos. Pero en el peor de los casos, será cerca de n pasos cuadrados de trabajo para ordenar la cubierta.

Ahora aquí es donde grande O es nuestro amigo.

Big O señala esto: a medida que n se hace grande, cuando clasificamos las tarjetas, el trabajo se vuelve MUCHO MÁS DIFÍCIL que el antiguo trabajo de solo agregar estas cosas. Cómo sabemos esto?

Bueno, si n se hace realmente grande, no nos importa lo que podamos agregar a n o n al cuadrado.

Para n grande, n al cuadrado es más grande que n.

Big O nos dice que ordenar las cosas es más difícil que agregar cosas. O (n al cuadrado) es más que O (n) para n grande. Eso significa que si n se hace muy grande, ordenar una baraja mixta de n cosas DEBE tomar más tiempo que simplemente agregar n cosas mezcladas.

Big O no resuelve el trabajo por nosotros. Big O nos dice lo difícil que es el trabajo.

Tengo un mazo de cartas. Yo los ordené. Tu ayudaste. Gracias.

¿Hay una manera más rápida de ordenar las cartas? ¿Puede el gran O ayudarnos?

Sí, hay una manera más rápida! Se necesita algo de tiempo para aprender, pero funciona ... y funciona bastante rápido. Puedes intentarlo también, pero tómate tu tiempo con cada paso y no pierdas tu lugar.

En esta nueva forma de ordenar un mazo, no verificamos pares de cartas como lo hicimos hace un tiempo. Aquí están tus nuevas reglas para ordenar este mazo:

Uno: Elijo una carta en la parte de la baraja en la que trabajamos ahora. Puedes elegir uno para mí si quieres. (La primera vez que hacemos esto, "la parte de la cubierta en la que trabajamos ahora" es toda la cubierta, por supuesto).

Dos: extiendo la baraja en esa carta que elegiste. ¿Qué es este espacio? ¿Cómo me extiendo? Bueno, voy desde la tarjeta de inicio hacia abajo, una por una, y busco una tarjeta que sea más alta que la tarjeta de distribución.

Tres: voy de la carta final hacia arriba, y busco una carta que sea más baja que la carta de distribución.

Una vez que he encontrado estas dos cartas, las cambio y luego busco más cartas para intercambiar. Es decir, vuelvo al paso dos y, en la tarjeta, eligió un poco más.

En algún momento, este bucle (de dos a tres) terminará. Termina cuando ambas mitades de esta búsqueda se encuentran en la tarjeta de distribución. Luego, acabamos de repartir el mazo con la carta que eligió en el primer paso. Ahora, todas las cartas cercanas al inicio son más bajas que la carta de distribución; y las tarjetas cerca del final son más altas que la tarjeta de distribución. ¡Buen truco!

Cuatro (y esta es la parte divertida): Tengo dos cubiertas pequeñas ahora, una más baja que la tarjeta de expansión y otra más alta. ¡Ahora voy al paso uno, en cada cubierta pequeña! Es decir, comienzo desde el paso uno en la primera cubierta pequeña, y cuando se realiza ese trabajo, comienzo desde el paso uno en la siguiente cubierta pequeña.

Divido la cubierta en partes y clasifico cada parte, más pequeña y más pequeña, y en algún momento no tengo más trabajo que hacer. Ahora esto puede parecer lento, con todas las reglas. Pero créeme, no es lento en absoluto. ¡Es mucho menos trabajo que la primera forma de ordenar las cosas!

¿Cómo se llama este tipo? ¡Se llama Quick Sort! Ese tipo fue hecho por un hombre llamado CAR Hoare y él lo llamó Quick Sort. Ahora, Quick Sort se usa todo el tiempo!

Quick Sort rompe las cubiertas grandes en las pequeñas. Es decir, rompe grandes tareas en las pequeñas.

Hmmm Puede haber una regla allí, creo. Para hacer grandes tareas pequeñas, divídalos.

Este tipo es bastante rápido. Que tan rapido Big O nos dice: este tipo necesita trabajo O (n log n), en el caso medio.

¿Es más o menos rápido que el primero? Big O, por favor ayuda!

El primer tipo fue O (n al cuadrado). Pero la ordenación rápida es O (n log n). Sabes que n log n es menor que n cuadrado, para big n, ¿verdad? Bueno, ¡así es como sabemos que Quick Sort es rápido!

Si tienes que ordenar una baraja, ¿cuál es la mejor manera? Bueno, puedes hacer lo que quieras, pero yo elegiría Orden rápido.

¿Por qué elijo Ordenación rápida? ¡No me gusta trabajar, claro! Quiero hacer el trabajo tan pronto como pueda hacerlo.

¿Cómo sé que la clasificación rápida es menos trabajo? Sé que O (n log n) es menor que O (n cuadrado). Las O son más pequeñas, por lo que la clasificación rápida es menos trabajo.

Ahora conoces a mi amigo, Big O. Él nos ayuda a hacer menos trabajo. Y si sabes O grande, ¡puedes hacer menos trabajo también!

¡Aprendiste todo eso conmigo! ¡Eres muy inteligente! Muchas gracias!

Ahora que el trabajo está hecho, vamos a jugar!

[1]: Hay una forma de hacer trampa y agregar todas las cosas de una a una, todas a la vez. Un niño llamado Gauss descubrió esto cuando tenía ocho años. Sin embargo, no soy tan inteligente, así que no me preguntes cómo lo hizo .

EDIT: Nota rápida, esto es casi seguro que confunde la notación Big O (que es un límite superior) con la notación Theta (que es tanto un límite superior como un límite inferior). En mi experiencia, esto es realmente típico de discusiones en entornos no académicos. Disculpas por cualquier confusión causada.

En una frase: a medida que aumenta el tamaño de su trabajo, ¿cuánto tiempo se tarda en completarlo?

Obviamente, eso es solo usar "tamaño" como entrada y "tiempo tomado" como salida; la misma idea se aplica si desea hablar sobre el uso de la memoria, etc.

Aquí hay un ejemplo donde tenemos camisetas N que queremos secar. Vamos a suponer que es increíblemente rápida para conseguir que en la posición de secado (es decir, la interacción humana es insignificante). Ese no es el caso en la vida real, por supuesto ...

Usando una línea de lavado afuera: asumiendo que usted tiene un patio trasero infinitamente grande, el lavado se seca en O (1) tiempo. Por mucho que tengas, obtendrá el mismo sol y aire fresco, por lo que el tamaño no afecta el tiempo de secado.
Usando una secadora: colocas 10 camisas en cada carga, y luego se terminan una hora más tarde. (Ignore los números reales aquí, son irrelevantes). Por lo tanto, secar 50 camisas toma aproximadamente 5 veces más que secar 10 camisas.
Poner todo en un armario de ventilación: si lo ponemos todo en una gran pila y dejamos que el calor general lo haga, las camisas intermedias tardarán mucho tiempo en secarse. No me gustaría adivinar los detalles, pero sospecho que esto es al menos O (N ^ 2): a medida que aumenta la carga de lavado, el tiempo de secado aumenta más rápido.

Un aspecto importante de la notación "O grande" es que no dice qué algoritmo será más rápido para un tamaño dado. Tome una tabla hash (clave de cadena, valor entero) frente a una matriz de pares (cadena, entero). ¿Es más rápido encontrar una clave en la tabla hash o un elemento en la matriz, basado en una cadena? (es decir, para la matriz, "encuentre el primer elemento donde la parte de la cadena coincida con la clave dada.") Las tablas hash generalmente se amortizan (~ = "en promedio") O (1): una vez que están configuradas, debería tomar aproximadamente al mismo tiempo para encontrar una entrada en una tabla de 100 entradas como en una tabla de 1,000,000 de entradas. Encontrar un elemento en una matriz (basado en el contenido en lugar de en el índice) es lineal, es decir, O (N): en promedio, tendrá que ver la mitad de las entradas.

¿Esto hace que una tabla hash sea más rápida que una matriz para búsquedas? No necesariamente.Si tiene una colección muy pequeña de entradas, una matriz puede ser más rápida; es posible que pueda verificar todas las cadenas en el tiempo que lleva calcular simplemente el código hash de la que está viendo. Sin embargo, a medida que el conjunto de datos crece, la tabla hash eventualmente vencerá la matriz.

Es muy difícil medir la velocidad de los programas de software y, cuando lo intentamos, las respuestas pueden ser muy complejas y estar llenas de excepciones y casos especiales. Este es un gran problema, porque todas esas excepciones y casos especiales nos distraen y no nos ayudan cuando queremos comparar dos programas diferentes entre sí para descubrir cuál es "más rápido".

Como resultado de toda esta complejidad inútil, las personas intentan describir la velocidad de los programas de software utilizando las expresiones más pequeñas y menos complejas (matemáticas) posibles. Estas expresiones son aproximaciones muy crudas: aunque, con un poco de suerte, capturarán la "esencia" de si una pieza de software es rápida o lenta.

Debido a que son aproximaciones, usamos la letra "O" (Big Oh) en la expresión, como una convención para indicar al lector que estamos realizando una simplificación excesiva. (Y para asegurarse de que nadie piense erróneamente que la expresión es de alguna manera precisa).

Si lee "Oh" como "en el orden de" o "aproximadamente", no se equivocará demasiado. (Creo que la elección del Big-Oh podría haber sido un intento de humor).

Lo único que intentan hacer estas expresiones "Big-Oh" es describir cuánto ralentiza el software a medida que aumentamos la cantidad de datos que el software debe procesar. Si duplicamos la cantidad de datos que deben procesarse, ¿el software necesita el doble de tiempo para finalizar su trabajo? ¿Diez veces más largo? En la práctica, hay un número muy limitado de expresiones de gran Oh que encontrarás y de las que debes preocuparte:

El bueno:

O(1) Constante : el programa tarda el mismo tiempo en ejecutarse sin importar cuán grande sea la entrada.
O(log n) Logarítmico : el tiempo de ejecución del programa aumenta solo lentamente, incluso con grandes aumentos en el tamaño de la entrada.

El malo:

O(n) Lineal : el tiempo de ejecución del programa aumenta proporcionalmente al tamaño de la entrada.
O(n^k) Polinomio : - El tiempo de procesamiento aumenta cada vez más rápido, como una función polinomial, a medida que aumenta el tamaño de la entrada.

... y lo feo

O(k^n) Exponencial El tiempo de ejecución del programa aumenta muy rápidamente incluso con aumentos moderados en el tamaño del problema; solo es práctico procesar pequeños conjuntos de datos con algoritmos exponenciales.
O(n!) Factorial El tiempo de ejecución del programa será más prolongado de lo que puede esperar, excepto los conjuntos de datos más pequeños y de apariencia más trivial.

La notación Big O es una forma de describir el límite superior de un algoritmo en términos de espacio o tiempo de ejecución. La n es la cantidad de elementos en el problema (es decir, el tamaño de una matriz, la cantidad de nodos en un árbol, etc.) Nos interesa describir el tiempo de ejecución cuando n crece.

Cuando decimos que algún algoritmo es O (f (n)), estamos diciendo que el tiempo de ejecución (o el espacio requerido por ese algoritmo) siempre es menor que algunos tiempos constantes f (n).

Decir que la búsqueda binaria tiene un tiempo de ejecución de O (logn) es decir que existe una constante c que puede multiplicar log (n) por que siempre será mayor que el tiempo de ejecución de la búsqueda binaria. En este caso, siempre tendrá un factor constante de comparaciones de log (n).

En otras palabras, donde g (n) es el tiempo de ejecución de su algoritmo, decimos que g (n) = O (f (n)) cuando g (n) <= c * f (n) cuando n> k, donde c y k son algunas constantes.

La notación Big O es una forma de describir la rapidez con la que se ejecutará un algoritmo dado un número arbitrario de parámetros de entrada, que llamaremos "n". Es útil en informática porque diferentes máquinas operan a diferentes velocidades, y simplemente decir que un algoritmo tarda 5 segundos no le dice mucho porque, aunque puede estar ejecutando un sistema con un procesador de núcleo octo de 4,5 Ghz, es posible que esté funcionando Un sistema de 15 años y 800 Mhz, que podría llevar más tiempo independientemente del algoritmo. Entonces, en lugar de especificar qué tan rápido se ejecuta un algoritmo en términos de tiempo, decimos qué tan rápido se ejecuta en términos de número de parámetros de entrada, o "n". Al describir los algoritmos de esta manera, podemos comparar las velocidades de los algoritmos sin tener que tener en cuenta la velocidad de la computadora en sí.

No estoy seguro de seguir contribuyendo al tema, pero aún pensé que lo compartiría: una vez encontré que esta publicación de blog tenía algunas explicaciones y ejemplos bastante útiles (aunque muy básicos) sobre Big O:

A través de ejemplos, esto ayudó a poner los fundamentos básicos en mi cráneo con forma de concha de tortuga, así que creo que es un bonito descenso de 10 minutos para que te dirijas en la dirección correcta.

Supongamos que estamos hablando de un algoritmo A , que debería hacer algo con un conjunto de datos de tamaño n .

Entonces O( <some expression X involving n> )significa, en inglés simple:

Si no tiene suerte al ejecutar A, puede tomar X (n) operaciones para completar.

Como sucede, hay ciertas funciones (piense en ellas como implementaciones de X (n) ) que tienden a ocurrir con bastante frecuencia. Estos son bien conocidos y fácilmente comparados (ejemplos: 1, Log N, N, N^2, N!, etc ..)

Al comparar estos al hablar de A y otros algoritmos, es fácil clasificar los algoritmos de acuerdo con el número de operaciones que pueden (en el peor de los casos) requerir para completar.

En general, nuestro objetivo será encontrar o estructurar un algoritmo A de tal manera que tenga una función X(n)que devuelva un número tan bajo como sea posible.

Supongamos que solicita Harry Potter: Complete 8-Film Collection [Blu-ray] de Amazon y descargue la misma colección de películas en línea al mismo tiempo. Quieres probar qué método es más rápido. La entrega tarda casi un día en llegar y la descarga se completa unos 30 minutos antes. ¡Genial! Así que es una carrera cerrada.

¿Qué pasa si pido varias películas en Blu-ray como El Señor de los Anillos, Crepúsculo, La trilogía del caballero oscuro, etc. y descargo todas las películas en línea al mismo tiempo? Esta vez, la entrega aún tarda un día en completarse, pero la descarga en línea tarda 3 días en finalizar. Para compras en línea, el número de artículo comprado (entrada) no afecta el tiempo de entrega. La salida es constante. A esto lo llamamos O (1) .

Para la descarga en línea, el tiempo de descarga es directamente proporcional a los tamaños de archivo de la película (entrada). A esto lo llamamos O (n) .

Por los experimentos, sabemos que las compras en línea escalan mejor que las descargas en línea. Es muy importante entender la notación O grande porque le ayuda a analizar la escalabilidad y la eficiencia de los algoritmos.

Nota: la notación Big O representa el peor escenario de un algoritmo. Supongamos que O (1) y O (n) son los peores escenarios del ejemplo anterior.

Referencia : http://carlcheo.com/compsci

Tengo una forma más sencilla de entender la complejidad de tiempo, la métrica más común para calcular la complejidad de tiempo es la notación Big O. Esto elimina todos los factores constantes para que el tiempo de ejecución se pueda estimar en relación con N a medida que N se acerca al infinito. En general se puede pensar así:

statement;

Es constante El tiempo de ejecución de la declaración no cambiará en relación con N

for ( i = 0; i < N; i++ ) statement;

Es lineal El tiempo de ejecución del bucle es directamente proporcional a N. Cuando N se duplica, también lo hace el tiempo de ejecución.

for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; }

Es cuadrático. El tiempo de ejecución de los dos bucles es proporcional al cuadrado de N. Cuando N se duplica, el tiempo de ejecución aumenta en N * N.

while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; }

Es logarítmico. El tiempo de ejecución del algoritmo es proporcional al número de veces que N puede dividirse por 2. Esto se debe a que el algoritmo divide el área de trabajo a la mitad con cada iteración.

void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); }

Es N * log (N). El tiempo de ejecución consiste en N bucles (iterativos o recursivos) que son logarítmicos, por lo que el algoritmo es una combinación de lineal y logarítmico.

En general, hacer algo con cada elemento en una dimensión es lineal, hacer algo con cada elemento en dos dimensiones es cuadrático, y dividir el área de trabajo por la mitad es logarítmica. Existen otras medidas de Big O como cúbica, exponencial y raíz cuadrada, pero no son tan comunes. La notación O grande se describe como O () donde es la medida. El algoritmo de ordenación rápida se describiría como O (N * log (N)).

Nota: nada de esto ha tenido en cuenta las mejores, las medidas promedio y el peor de los casos. Cada uno tendría su propia notación Big O. También tenga en cuenta que esta es una explicación muy simplista. Big O es el más común, pero también es más complejo de lo que he mostrado. También hay otras notaciones como omega grande, o pequeña y theta grande. Probablemente no los encontrará fuera de un curso de análisis de algoritmos.

Ver más en: Here