Prefiero la menor definición formal posible y las matemáticas simples.

Nota rápida, 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 las discusiones en entornos no académicos. Disculpas por cualquier confusión causada.

La gran complejidad de 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 elegidas deliberadamente en esa oración:

• relativo: solo puedes comparar manzanas con manzanas. No puede comparar un algoritmo para hacer multiplicación aritmética con 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 dará 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 en función de las operaciones de comparación (comparar 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 lleva 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. Toma 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 resolverlos se llama algoritmo .

La adición es la más simple. Alinea los números hacia arriba (a la derecha) y agrega los dígitos en una columna escribiendo el último número de esa suma en el resultado. La parte 'decenas' 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 que para sumar estos dos números juntos tengamos que sumar 6 dígitos (y posiblemente llevar un séptimo). Si sumamos dos números de 100 dígitos, tenemos que hacer 100 sumas. Si agregamos dos números de 10,000 dígitos, tenemos que hacer 10,000 sumas.

¿Ves el patrón? La complejidad (que es el número de operaciones) es directamente proporcional al número de dígitos n en el número mayor. Llamamos a esto O (n) o complejidad lineal .

La resta es similar (excepto que puede que necesite pedir prestado en lugar de llevar).

La multiplicación es diferente. Alinee los números, tome el primer dígito en el número inferior y multiplíquelo por turnos contra 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 billón (10 ¹² ) de 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 presentar 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 viste en nuestro ejemplo con dos números de un millón de dígitos cada uno, el segundo término (2n) se vuelve insignificante (representa el 0.0002% del total de operaciones en esa etapa).

Uno puede notar que hemos asumido el peor de los casos aquí. Al multiplicar números de 6 dígitos, si uno de ellos tiene 4 dígitos y el otro tiene 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 trata sobre el peor de los casos de un algoritmo.

La guía telefónica

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

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

Una aplicación típica podría ser abrir hasta la mitad, tomar el 500 000 ^º y compararlo con "Smith". Si resulta ser "Smith, John", tenemos mucha suerte. Mucho más probable es que "John Smith" aparezca antes o después de ese nombre. Si es después, dividimos la última mitad de la guía telefónica a la mitad y repetimos. Si es antes, dividimos la primera mitad de la guía telefónica a la mitad y repetimos. Y así.

Esto se llama 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 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 se necesita 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 que siga siendo O (log n) al igual que O (2n ² ) y O (100n ² ) siguen siendo O (n ² ).

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

• Mejor caso: en la búsqueda de la guía telefónica, el mejor caso es que encontremos el nombre en una comparación. Esto es O (1) o complejidad constante ;
• Caso esperado: Como se discutió 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á más importante.

De vuelta a la guía telefónica.

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

Empiezas con el primer nombre y compara el número. Si es un partido, genial, si no, pasas al siguiente. Debe 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) (por 500,000); y
• 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 ciudades. 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 tiene 3 ciudades A, B y C con carreteras entre todos los pares, entonces podría 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 estos son equivalentes (A → B → C y C → B → A son equivalentes, por ejemplo, porque usan los mismos caminos, solo al revés).

En la actualidad, hay 3 posibilidades.

• Lleva esto a 4 ciudades y tienes (iirc) 12 posibilidades.
• Con 5 son 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 ⁶⁴

Entonces, el gran problema del vendedor ambulante es O (n!) O complejidad factorial o combinatoria .

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 del que quería hacer una mención rápida es que cualquier algoritmo que tenga una complejidad de O (n ^a ) se dice que tiene complejidad polinómica o se puede resolver en tiempo polinómico .

O (n), O (n ² ) etc. son todos tiempo polinómico. Algunos problemas no se pueden resolver en tiempo polinómico. Ciertas cosas se usan en el mundo debido a esto. La criptografía de clave pública es un excelente 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 para mi explicación (con suerte en inglés simple) de Big O (revisada)

Muestra cómo se escala un algoritmo según el tamaño de entrada.

O (n ² ) : conocida 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 entonces 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 entonces 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, suponiendo que cada cálculo tome 1 segundo, el registro de la entrada nes el tiempo requerido, por lo tanto log n.

Esa es la esencia de esto. Reducen las matemáticas hacia abajo, por lo que podría no ser exactamente n ² o lo que sea que digan, pero ese será el factor dominante en la escala.

La notación Big-O (también llamada notación de "crecimiento asintótico") es lo que las funciones "parecen" cuando ignora factores constantes y cosas cerca del origen . Lo usamos para hablar sobre cómo escala la cosa .

Lo esencial

para entradas "suficientemente" grandes ...

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

La notación big-O no se preocupa por factores constantes: 9x²se dice que la función "crece exactamente como" 10x². A la notación asintótica big-O tampoco le importan las cosas no asintóticas ("cosas cerca del origen" o "lo que sucede cuando el tamaño del problema es pequeño"): 10x²se dice que la función "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 eclipsados ​​por las grandes partes de la ecuación cuando consideras escalas cada vez más grandes; su contribución se vuelve enana e irrelevante. (Consulte la sección de ejemplos).

Dicho de otra manera, se trata de la relación a medida que avanza hasta el infinito. Si divide el tiempo real que toma entre O(...), obtendrá un factor constante en el límite de entradas grandes. Intuitivamente, esto tiene sentido: las funciones se "escalan" entre sí si se puede multiplicar una para obtener la otra. Ahí es 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 "suficientemente grandes" N (si ignoramos cosas cerca del origen), existe alguna 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" opción se conoce como el "factor constante" del algoritmo ... pero a menudo lo ignoramos como si ignoramos los términos que no son más grandes (consulte la sección Factores constantes para saber por qué no suelen importar). 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 nos importa mucho) " .

En general, O(...)es el más útil porque a menudo nos importa el comportamiento en el peor de los casos. Si f(x)representa algo "malo" como el uso del procesador o la memoria, entonces " f(x) ∈ O(upperbound)" significa " upperboundes el peor de los casos del uso del procesador / memoria".

Aplicaciones

Como 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 las asintóticas de cualquier cosa donde el escalado sea significativo, como:

• el número de posibles apretones de manos entre Npersonas en una fiesta ( Ɵ(N²)específicamente N(N-1)/2, pero lo que importa es que "escala" N²)
• número esperado probabilístico de personas que han visto algo de marketing viral en función del tiempo
• cómo la latencia del sitio web se escala con el número de unidades de procesamiento en una CPU o GPU o grupo de computadoras
• cómo se reduce la producción de calor en la CPU en función del recuento de transistores, voltaje, etc.
• cuánto tiempo necesita ejecutar un algoritmo, en función del tamaño de entrada
• cuánto espacio necesita ejecutar un algoritmo, en función del tamaño de entrada

Ejemplo

Para el ejemplo de apretón de manos anterior, 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-choose-2 o N*(N-1)/2(cada una de las N personas le da la mano a N-1 a otras personas, pero este apretón de manos cuenta dos veces, así que divida por 2):

Sin embargo, para un gran número de personas, el término lineal Nes enano y efectivamente contribuye 0 a la relación (en la tabla: la fracción de cuadros vacíos en la diagonal sobre los cuadros totales se reduce a medida que aumenta el número de participantes). Por lo tanto, el comportamiento de escala 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 (N * (N-1) / 2 marcas de verificación) ni siquiera estuvieran allí (N ² marcas ^de verificación asintóticamente).

(digresión temporal del "inglés simple" :) Si quisieras probar esto a ti mismo, podrías realizar un poco de álgebra simple en la proporción para dividirlo en varios términos ( limsignifica "considerado en el límite de", simplemente ignóralo si no lo he visto, es solo una notación para "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' x² tanto para valores grandes, que si escribiéramos la proporción # handshakes / x², el hecho de que no necesitamos exactamente apretones de manos x² ni siquiera aparecería en el decimal por un tiempo arbitrariamente grande.

por ejemplo, para x = 1 millón, relación # apretones de manos / x²: 0.499999 ...

Construyendo Intuición

Esto nos permite hacer declaraciones como ...

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

• ... Doblo el tiempo que tarda un algoritmo O (N) ("tiempo lineal") ".

  N → (2N) = 2 ( N )

• ... I doble cuadrado (cuádruple) el tiempo que tarda 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² )

• ... Doblé en cubos (octuple) el tiempo que tarda un algoritmo O (N³) ("tiempo cúbico") " (p . Ej., Un problema 100x tan grande toma 100³ = 1000000x tanto tiempo ... muy insostenible)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... Agrego una cantidad fija al tiempo que tarda un 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 tarda un algoritmo O (1) ("tiempo constante") " (¡el más barato!)

  c * 1 → c * 1

• ... "(básicamente) doblo" 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 ) ............ dicho de otra manera ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[para los matemáticamente inclinados, puede pasar el mouse sobre los spoilers para notas secundarias menores]

(con crédito a https://stackoverflow.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 anteriores (por ejemplo, en el registro (N)) de modo que no sea así)

Estas son las órdenes de crecimiento básicas que los programadores y los informáticos aplicados utilizan como puntos de referencia. Los ven todo el tiempo. (Por lo tanto, aunque técnicamente podría pensar "Duplicar la entrada hace que un algoritmo O (√N) sea 1.414 veces más lento", es mejor pensar que "esto 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 el doble de 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 acto de elegir un algoritmo con un mejor Big-O a menudo mejorará el rendimiento en órdenes de magnitud.

Algunos algoritmos asintóticamente superiores (por ejemplo, un tipo de no comparación O(N log(log(N)))) pueden tener un factor constante tan grande (por ejemplo 100000*N log(log(N))), o una sobrecarga que es relativamente grande como O(N log(log(N)))con un oculto + 100*N, que rara vez vale la pena usarlos incluso en "datos grandes".

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

O(N)los algoritmos son, en cierto sentido, los "mejores" algoritmos si necesita leer todos sus datos. El acto mismo de leer un montón de datos es una O(N)operació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 dato (o incluso cualquier otro dato), su algoritmo tomará O(N)tiempo para realizar este examen. No importa cuánto tiempo tome su algoritmo real, será al menos O(N)porque pasó ese tiempo mirando todos los datos.

Lo mismo puede decirse del acto mismo 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 cartas 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)tiempo), además de una cantidad arbitraria de preprocesamiento (por ejemplo, O(N)or O(N log(N))o O(N²)) que intentamos 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)o O(log(N)). ¡Luego procedes a hacer una gran cantidad de consultas! En general, cuanto más trabajo esté dispuesto a hacer por adelantado, 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 carretera y quería encontrar todas las intersecciones de calles.

• Método ingenuo: si tuviera las coordenadas de una intersección de calles y quisiera examinar las calles cercanas, tendría que atravesar millones de segmentos cada vez y verificar la adyacencia de cada uno.
• Si solo necesitara hacer esto una vez, no sería un problema tener que hacer el método ingenuo de O(N)trabajo solo una vez, pero si desea hacerlo muchas veces (en este caso, Nveces, una vez para cada segmento), nosotros tendría que hacer el O(N²)trabajo, 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 hashmap o diccionario), pagamos un pequeño costo al preprocesar todo a O(N)tiempo. 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ículas adyacentes de los cuales solo hay 9, que es un constante).
• Nuestra tarea pasó de ser inviable O(N²)a manejable O(N), 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 algunas propiedades de los datos. Si nuestros segmentos de carretera son como piezas de rompecabezas, los agrupamos combinando el color y el patrón. Luego explotamos esto para evitar hacer un trabajo adicional más tarde (comparar piezas de rompecabezas de un color similar entre sí, no con cada una de las piezas del rompecabezas).

La moraleja de la historia: una estructura de datos nos permite acelerar las operaciones. Aún más, las estructuras de datos avanzadas pueden permitirle combinar, retrasar o incluso ignorar operaciones de maneras increíblemente inteligentes. Diferentes problemas tendrían diferentes analogías, pero todos implicarían organizar los datos de una manera que explote alguna estructura que nos interesa, o que hemos impuesto artificialmente para la contabilidad. Trabajamos con anticipación (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 las cosas se escalan y se pueden usar en muchos campos diferentes. Dicho esto ... así es como se aplica la notación asintótica a la codificación.

Lo básico: cada vez que interactuamos con cada elemento de una colección de tamaño A (como una matriz, un conjunto, todas las teclas de un mapa, etc.), o realizamos iteraciones A de un bucle, eso es un factor multiplicativo de 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: la cantidad de iteraciones, el trabajo realizado en el bucle (o para funciones: la cantidad de veces que se llama función, tiempos de trabajo realizados en la función). (Esto se cumple si no hacemos nada elegante, como omitir bucles o salir temprano del bucle, o cambiar el flujo de control en la función en función de argumentos, lo cual es muy común). Aquí hay algunos ejemplos de técnicas de visualización, con el pseudocódigo que lo acompaña.

(aquí, los xs representan unidades de trabajo de tiempo constante, instrucciones de procesador, códigos de operación de intérpretes, lo que sea)

for(i=0; i<A; i++)        // A * ...
    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 * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        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 *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Si hacemos algo un poco complicado, aún puede imaginarse visualmente lo que está sucediendo:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

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___________________|

Aquí, el contorno reconocible más pequeño que puede dibujar es lo que importa; un triángulo es una forma bidimensional (0.5 A ^ 2), al igual que 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 que no menciono 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 los amamos. Sin embargo, podemos ver que la forma en que tejimos bucles y funciones y condicionales junto con nuestros datos (flujo de control, etc.) imita el uso de tiempo y espacio 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 fácil o una estructura de datos 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 suposición ingenua en el peor de los casos.

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 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 hace log (N) pasa 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 mencionar nuevamente: si realizamos un hash (por ejemplo, una búsqueda de diccionario / tabla 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 divide y vencerás, puedes usar el Teorema maestro (generalmente funciona) o, en casos ridículos, el Teorema de Akra-Bazzi (casi siempre funciona) , busca el 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 extremadamente ineficiente? ". Si la respuesta es "sí" Y usted prevé que realmente importa, entonces puede dar un paso atrás y pensar en varios trucos para 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 de casos amortizados y promedio

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 usar la notación big-O 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 habitual O(N log(N))(las entradas realmente malas son muy pequeñas en número, tan pocas que no las notamos en el caso promedio).

El peor de los casos amortizado : algunas estructuras de datos pueden tener una complejidad en el peor de los casos que es grande, pero garantiza que si realiza muchas de estas operaciones, la cantidad promedio de trabajo que realiza será mejor que el peor de los casos. Por ejemplo, puede tener una estructura de datos que normalmente toma O(1)tiempo constante . Sin embargo, ocasionalmente 'hipo' y tomará O(N)tiempo para una operación aleatoria, porque tal vez necesite hacer algo de contabilidad o recolección de basura o algo así ... pero le promete que si tiene hipo, no volverá a tener hipo para N Más operaciones. El peor de los casos sigue siendo O(N)por operación, pero el costo amortizado en muchas ejecuciones 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 combina 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 asintóticamente.

La analogía para el análisis amortizado:

Tú conduces un auto. 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 hasta 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 pasó conduciendo a la estación de servicio se "amortizan" en una cantidad suficientemente grande de viajes, que puede ignorarlo y pretender que todos sus viajes fueron tal vez un 5% más largos.

Comparación entre el caso medio y el peor caso amortizado:

• Caso medio: hacemos algunas suposiciones sobre nuestras entradas; es decir, si nuestras entradas tienen diferentes probabilidades, nuestras salidas / tiempos de ejecución tendrán diferentes probabilidades (de las cuales tomamos el promedio). Por lo general, suponemos 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 promedio / tiempo de ejecución pueden no tener sentido. Sin embargo, si anticipa entradas uniformemente aleatorias, ¡es útil pensar en esto!
• El peor de los casos amortizado: si utiliza una estructura de datos amortizada del peor de los casos, se garantiza que el rendimiento estará dentro del peor de los casos amortizado ... eventualmente (incluso si las entradas son elegidas por un demonio malvado que lo sabe todo y está tratando de jódete) Por lo general, usamos esto para analizar algoritmos que pueden tener un rendimiento muy `` irregular '' con grandes contratiempos inesperados, pero que con el tiempo funcionan tan bien como otros algoritmos. (Sin embargo, a menos que su estructura de datos tenga límites superiores para mucho trabajo sobresaliente en el que esté dispuesto a postergar, un atacante malvado quizás podría obligarlo 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 teniendo en cuenta la escala.

(Consulte la Diferencia entre el caso promedio y el análisis 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 llevar 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 big-O no es toda la historia. Puede acelerar drásticamente algunos algoritmos utilizando el almacenamiento en caché, haciéndolos ajenos a la memoria caché, evitando cuellos de botella al trabajar con RAM en lugar de disco, utilizando paralelización o trabajando con anticipación: estas técnicas a menudo son independientes del orden de crecimiento notación "big-O", aunque a menudo verá el número de núcleos en la notación big-O de algoritmos paralelos.

También tenga en cuenta que debido a las limitaciones 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á ordenando algo así como 5 elementos, no desea utilizar la rápida selección O(N log(N))rápida; desea utilizar el orden de inserción, que funciona bien en entradas pequeñas. Estas situaciones a menudo surgen en algoritmos de divide y vencerás, donde divides el problema en subproblemas cada vez más pequeños, como la clasificación recursiva, las transformaciones rápidas de Fourier o la multiplicación de matrices.
• Si algunos valores están efectivamente delimitados debido a algún hecho oculto (p. Ej., El nombre humano promedio tiene un límite suave de quizás 40 letras y la edad humana tiene un límite suave de aproximadamente 150). También puede imponer límites a su entrada para que los términos sean constantes de manera efectiva.

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

Los programas también se ejecutarán más lentamente en una computadora de 500MHz frente a una computadora de 2GHz. Realmente no consideramos esto como parte de los límites de los 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 afectar 'secretamente' el rendimiento, como si se está ejecutando bajo emulación o si el compilador optimizó el código o no. Esto puede hacer que algunas operaciones básicas tarden más (incluso entre sí), o incluso acelerar o ralentizar algunas operaciones de forma asintótica (incluso entre sí). El efecto puede ser pequeño o grande entre diferentes implementaciones y / o entornos. ¿Cambias idiomas o máquinas para ganar ese pequeño trabajo extra? Eso depende de otras cien razones (necesidad, habilidades, compañeros de trabajo, productividad del programador,

Los problemas anteriores, como el efecto de la elección de qué lenguaje de programación se usa, casi nunca se consideran parte del factor constante (ni deberían serlo); Sin embargo, uno debe ser consciente de ellos porque a veces (aunque rara vez) 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 find-min); ¿Utilizas 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 a veces no.

( editar : La explicación del "inglés simple" termina aquí).

Apéndices matemáticos

Para completar, la definición precisa de la notación big-O es la siguiente: f(x) ∈ O(g(x))significa que "f está asintóticamente limitado por const * g": ignorando todo por debajo de un valor finito de x, existe una constante tal que |f(x)| ≤ const * |g(x)|. (Los otros símbolos son los siguientes: al 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))(acotado superior e inferior 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 más o menos equivalente a==. (Lo siento, elegí retrasar la mención de los símbolos de valor absoluto hasta ahora, por razones de claridad; especialmente porque nunca he visto aparecer valores negativos en un contexto informático).

La gente lo usará con frecuencia = O(...), que es quizás la notación 'comp-sci' más correcta y totalmente legítima de usar; "f = O (...)" se lee "f es orden ... / f está limitado por xxx por ..." y se considera como "f es alguna expresión cuyos asintóticos son ...". Me enseñaron a usar el más riguroso ∈ O(...). ∈significa "es un elemento de" (aún leído como antes). 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.

O y Ω no son simétricos (n = O (n²), pero n² no es O (n)), pero Ɵ es simétrica y (dado que estas relaciones son todas transitivas y reflexivas) Ɵ, por lo tanto, es simétrica y transitiva y reflexiva y, por lo tanto, divide el conjunto de todas las funciones en clases de equivalencia . Una clase de equivalencia es un conjunto de cosas que consideramos iguales. Es decir, dada cualquier función que se te ocurra, puedes encontrar un 'representante asintótico' canónico / único de la clase (generalmente tomando el límite ... creo ); al igual que puede agrupar todos los enteros en cuotas o pares, puede agrupar todas las funciones con Ɵ en x-ish, log (x) ^ 2-ish, etc., ignorando básicamente los términos más pequeños (pero a veces puede estar atascado con funciones más complicadas que son clases separadas en sí mismas).

La =notación podría ser la más común e incluso se utiliza en documentos de científicos informáticos de renombre mundial. Además, a menudo se da el caso de que en un entorno informal, las personas dirán O(...)cuándo quieren 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. ;-)

EDITAR: Nota rápida, 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 superior e inferior). En mi experiencia, esto es realmente típico de las discusiones en entornos no académicos. Disculpas por cualquier confusión causada.

En una oración: a medida que aumenta el tamaño de su trabajo, ¿cuánto tiempo lleva completarlo?

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

Aquí hay un ejemplo donde tenemos N camisetas 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: suponiendo que tenga un patio trasero infinitamente grande, el lavado se seca en O (1) tiempo. Por mucho que tenga, obtendrá el mismo sol y aire fresco, por lo que el tamaño no afecta el tiempo de secado.

• Usando una secadora: pones 10 camisas en cada carga, y luego se hacen 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 ventilado: si ponemos todo en una gran pila y simplemente dejamos que el calor general lo haga, las camisas del medio tardarán mucho 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 determinado. 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 se configuran, debería tomar aproximadamente al mismo tiempo para encontrar una entrada en una tabla de 100 entradas que en una tabla de 1,000,000 de entradas. Encontrar un elemento en una matriz (basado en el contenido en lugar del índice) es lineal, es decir, O (N): en promedio, tendrá que mirar 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: puede verificar todas las cadenas en el tiempo necesario para calcular el código hash de la que está viendo. Sin embargo, a medida que el conjunto de datos crece, la tabla hash eventualmente vencerá a la matriz.

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 se duplica, el tiempo de ejecución se cuadruplica

• 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 necesarios para representar la entrada.

Los programadores usan la notación Big O más comúnmente como una medida aproximada de cuánto tiempo tomará completar una computación (algoritmo) expresada en función del tamaño del conjunto de entrada.

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

Más precisamente, la notación Big O se usa para expresar el comportamiento asintótico de una función. Eso significa cómo se comporta la función a medida que se acerca al infinito.

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

• O (1) : el tiempo de finalización 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 requieren aproximadamente el doble de 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 que se 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 dura 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 en el número de elementos multiplicado por el resultado de Log2 (N). Un ejemplo de esto es la ordenación en montón y la ordenación rápida .
• O (N ^ 2) : el tiempo para completar es aproximadamente igual al cuadrado del número de elementos. Un ejemplo de esto es el tipo de 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 multiplican por la función simplemente se ignoran.

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

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

O (n) significa Big O es n, y ahora podrías pensar, "¿Qué es n !?" Bueno "n" es la cantidad de elementos. Imaging que desea buscar un artículo 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, por lo que para ser genérico, decimos "¡oh, oye, n es una cantidad justa de valores!" .

Entonces, quizás entiendas lo que significa "n ² ", pero para ser aún más específico, juega con el pensamiento de que tienes un algoritmo de clasificación simple y simple; ordenamiento de burbuja. Este algoritmo necesita mirar a través de la lista completa, para cada elemento.

Mi lista

1. 1
2. 6 6
3. 3

El flujo aquí sería:

• Compara 1 y 6, ¿cuál es el más grande? Ok 6 está en la posición correcta, ¡avanza!
• Compara 6 y 3, ¡oh, 3 es menos! Pasemos a eso, Ok, la lista cambió, ¡tenemos que comenzar desde el principio ahora!

Esto es O n ² porque, debe mirar todos los elementos de la lista, hay elementos "n". Para cada elemento, observa todos los elementos una vez más, para comparar, esto también es "n", por lo que para cada elemento, busca "n" veces, lo que significa n * n = n ²

Espero que sea tan simple como quieras.

Pero recuerde, Big O es solo una forma de experimentar en el tiempo y el espacio.

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

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

Considere la diferencia entre una máquina de vapor y un cohete. No son simplemente variedades diferentes de la misma cosa (como, por ejemplo, un motor Prius frente a un motor Lamborghini) sino que son, en esencia, sistemas de propulsión dramáticamente diferentes. Una máquina de vapor puede ser más rápida que un cohete de juguete, pero ninguna máquina 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 escala con respecto a la relación de combustible requerido ("uso de recursos") para alcanzar una velocidad dada ("tamaño de entrada").

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

Considere el ejemplo de clasificación canónica. Bubble-sort es O (n ² ) mientras que merge-sort 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 clasificación de fusió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, entonces 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 descubre que puede tener que clasificar diez millones de elementos, entonces lo que esperaría es que la aplicación B en realidad termine siendo miles de veces más rápida que la aplicación A en este caso, debido completamente a la escala de cada algoritmo.

Aquí está el bestiario inglés simple que suelo usar para explicar las variedades comunes de Big-O

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

O (1):

Sin crecimiento. Independientemente de cuán grande sea el problema, puede resolverlo en la misma cantidad de tiempo. Esto es algo análogo a la transmisión en la que se necesita la misma cantidad de energía para transmitir en una distancia dada, independientemente de la cantidad 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 fines prácticos, puede considerar esto como una escala constante muy grande. La diferencia en el trabajo entre procesar mil y mil millones de artículos es solo un factor seis.

O ( n ):

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

O ( n log n ):

Esta complejidad es muy similar a O ( n ) . A todos los efectos prácticos, los dos son equivalentes. Este nivel de complejidad generalmente aún se consideraría escalable. Al ajustar las suposiciones, algunos algoritmos O ( n log n ) pueden transformarse en algoritmos O ( n ) . Por ejemplo, limitar el tamaño de las claves 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 costoso. La mayoría de las soluciones escalables no pueden usar algoritmos con este nivel de complejidad sin hacer gimnasia significativa. Esto generalmente se aplica a todas las demás complejidades polinómicas - O ( n ^k ) - también.

O (2 ⁿ ):

No escala No tiene 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 es una medida de cuánto tiempo / espacio utiliza un algoritmo en relación con el tamaño de su entrada.

Si un algoritmo es O (n), entonces 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í.

¿Cuál es una explicación sencilla en inglés de Big O? Con la menor definición formal posible y matemática simple.

Una explicación sencilla en inglés de la necesidad de 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 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 que lleva ejecutar un algoritmo. 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 simple de lo que es la notación Big O:

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

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 distraen y no 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 un software es rápido o lento.

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 haciendo una simplificación excesiva. (Y para asegurarse de que nadie piense erróneamente que la expresión es de alguna manera precisa).

Si lees el "Oh" como "en el orden de" o "aproximadamente" no te equivocarás 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 se ralentiza el software a medida que aumentamos la cantidad de datos que el software tiene que procesar. Si duplicamos la cantidad de datos que deben procesarse, ¿necesita el software el doble de tiempo para terminar su trabajo? ¿Diez veces más? En la práctica, hay un número muy limitado de expresiones big-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 crece cada vez más rápido, como una función polinómica, 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 con aumentos incluso 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 largo de lo que puede permitirse esperar cualquier cosa que no sean los conjuntos de datos más pequeños y aparentemente triviales.

Una respuesta simple y directa 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.

Ok, mis 2 centavos.

Big-O, es la tasa de aumento de los recursos consumidos por el programa, wrt problem-instance-size

Recurso: Podría ser el tiempo total de la CPU, podría ser el espacio máximo 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 la entrada 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)

Digamos 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, iteraciones totales = 3 * 3 = 9

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

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

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. El n es el número de elementos en el problema (es decir, el tamaño de una matriz, el número de nodos en un árbol, etc.) Estamos interesados ​​en describir el tiempo de ejecución a medida que n crece.

Cuando decimos que algún algoritmo es O (f (n)) estamos diciendo que el tiempo de ejecución (o 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á algún factor constante de comparaciones 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.

" ¿Cuál es una explicación sencilla en inglés de Big O? Con la menor definición formal posible y matemática simple " .

Una pregunta tan bella y simple parece al menos merecer una respuesta igualmente corta, 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 las personas siempre querrán más , ya sea que vivan hoy o mañana)

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

• Hablando en términos prácticos, el análisis de Big O es muy útil e importante porque Big O se enfoca directamente en la propia complejidad del algoritmo e ignora por completo cualquier cosa que sea simplemente una constante de proporcionalidad, como un motor de JavaScript, la velocidad de una CPU, su conexión a Internet y todas esas cosas que se hacen se vuelven rápidamente obsoletos irrisoriamente como un Modelo T . Big O se enfoca en el rendimiento solo de la misma manera que es igual de importante para las personas que viven en el presente o 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 forma de lograr resultados más allá del lento avance de la tecnología es inventar un mejor 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, entonces devuelve True,

• Si el ciclo ha finalizado sin encontrar la clave, devuelve False.

La notación Big-O representa el límite superior de la Complejidad (Tiempo, Espacio, ..)

Para encontrar la complejidad de Big-O on Time:

• Calcule cuánto tiempo (con respecto al tamaño de entrada) toma el peor de los casos:

• Peor de los casos: la clave no existe en la lista.

• Tiempo (peor de los casos) = 4n + 1

• Tiempo: O (4n + 1) = O (n) | en Big-O, las constantes se descuidan

• O (n) ~ Lineal

También está Big-Omega, que representa la complejidad del Mejor Caso:

• Best-Case: la clave es el primer elemento.

• Tiempo (mejor caso) = 4

• Tiempo: Ω (4) = O (1) ~ Instantáneo \ Constante

Big O

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

1. f (x) = k (x) g (x)

2. k está acotado en algún vecindario de a (si a = + ∞, esto significa que hay números N y M tales 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 gy alguna función acotada.

Pequeño o

Por cierto, aquí hay una comparación de la definición de o pequeño.

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

1. f (x) = k (x) g (x)

2. 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)). Del mismo modo, 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 notación Big O es una forma de describir qué tan rápido se ejecutará un algoritmo dado un número arbitrario de parámetros de entrada, que llamaremos "n". Es útil en informática porque las diferentes máquinas funcionan a diferentes velocidades, y simplemente decir que un algoritmo tarda 5 segundos no te dice mucho porque si bien puedes estar ejecutando un sistema con un procesador octo-core de 4.5 Ghz, puedo estar ejecutando un sistema de 15 años y 800 Mhz, que podría tomar 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 misma.

No estoy seguro de seguir contribuyendo al tema, pero aún así pensé en compartir: 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 obtener lo básico en mi cráneo con forma de carey, así que creo que es una lectura de 10 minutos bastante descendente para que te dirijas en la dirección correcta.

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

Entonces, para hablar de la gran O, usaré palabras que solo tienen un ritmo. Un sonido por palabra. Las palabras pequeñas son rápidas. Usted conoce estas palabras, y yo también. Usaremos palabras con un solo sonido. Ellos son pequeños. ¡Estoy seguro de que sabrá todas las palabras que usaremos!

Ahora, hablemos tú y yo del trabajo. La mayoría de las veces, no me gusta el trabajo. Te gusta el trabajo Puede ser el caso, pero estoy seguro de que no.

No me gusta ir a trabajar. No me gusta pasar tiempo en el trabajo. Si me saliera con la mía, 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 trabajar! Puedo jugar la mayor parte del tiempo, si sé O grande. ¡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 lo sé. Me perdí. Es muy difícil para mí hacerlo en mi cabeza. No me importa mucho este tipo de trabajo.

Así que no hagamos el trabajo. Vamos a pensar tú y yo en lo difícil que es. ¿Cuánto trabajo tendría que hacer para sumar seis números?

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

Aquí viene la gran O, para decirnos cuán difícil es esta matemática.

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

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

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

¡Ahora me piden que agregue del uno al diez! ¿Por qué habría de hacer eso? No quería agregar uno a seis. Agregar de uno a diez ... bueno ... ¡eso 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 sumar de uno a diez, que de uno a seis!

No quiero agregar en este momento. Solo quiero pensar en lo difícil que puede ser agregar tanto. Y espero jugar lo antes posible.

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

Big O es tu amigo y el mío. Big O nos ayuda a pensar en cuánto trabajo tenemos que hacer, para que podamos planificar. Y, si somos amigos de O grande, ¡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? ¿Extrañé 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. ¿Eras tú? ¿No? Oh bien. Entonces no podemos hacer el trabajo. Uf.

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

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

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

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

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

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

Ergh ¡Eso suena como un monton de trabajo!

¿Cómo podemos clasificar este mazo? Tengo un plan.

Examinaré cada par de cartas, par por par, a través de la baraja, de la primera a la última. Si la primera carta de un par es grande y la siguiente carta de ese par es pequeña, las cambio. De lo contrario, voy al siguiente par, y así sucesivamente ... y pronto, el mazo está terminado.

Cuando el mazo está terminado, pregunto: ¿intercambié 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á intercambios, y nuestro tipo de mazo estaría listo. ¡Mucho trabajo!

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

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

Big O, ayúdame!

Big O entra y dice: para un mazo de n cartas, para ordenarlo de esta manera se hará en tiempo O (N al cuadrado).

¿Por qué dice él al cuadrado?

Bueno, sabes que n al cuadrado es n veces n. Ahora lo entiendo: n cartas marcadas, hasta lo que podría ser n veces en el mazo. Eso es dos bucles, cada uno con n pasos. Eso es n cuadrado mucho trabajo por hacer. ¡Mucho trabajo, seguro!

Ahora, cuando O grande dice que tomará trabajo O (n al cuadrado), no quiere decir n al cuadrado suma, en la nariz. Puede ser un poco menos, en algún caso. Pero en el peor de los casos, será cerca de n pasos cuadrados de trabajo para clasificar el mazo.

Ahora aquí es donde O grande es nuestro amigo.

Big O señala esto: a medida que n crece, cuando clasificamos las tarjetas, el trabajo se vuelve MUCHO MÁS DURO 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: si n se hace realmente grande, ordenar un mazo mixto de n cosas DEBE tomar más tiempo, que simplemente agregar n cosas mixtas.

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

Tengo una baraja de cartas. Los clasifiqué. Tu ayudaste. Gracias.

¿Hay una forma más rápida de ordenar las tarjetas? ¿O grande puede ayudarnos?

Sí, hay una manera más rápida! Toma tiempo aprender, pero funciona ... y funciona bastante rápido. También puedes probarlo, 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 del mazo en la que trabajamos ahora" es todo el mazo, por supuesto).

Dos: abro el mazo en la carta que elegiste. ¿Qué es este juego? ¿Cómo me juego? Bueno, voy desde la tarjeta de inicio hacia abajo, uno por uno, y busco una tarjeta que sea más alta que la carta de juego.

Tres: voy desde la carta final hacia arriba y busco una carta que sea más baja que la carta extendida.

Una vez que he encontrado estas dos cartas, las cambio y continúo buscando más cartas para intercambiar. Es decir, vuelvo al paso dos, y despliego en la tarjeta que elegiste un poco más.

En algún momento, este ciclo (de dos a tres) terminará. Termina cuando las dos mitades de esta búsqueda se encuentran en la carta de juego. Luego, acabamos de desplegar el mazo con la carta que elegiste en el paso uno. Ahora, todas las cartas cerca del inicio son más bajas que la carta de juego; y las cartas cerca del final son más altas que la carta de juego. ¡Buen truco!

Cuatro (y esta es la parte divertida): ahora tengo dos mazos pequeños, uno más bajo que la carta de juego y otro más alto. ¡Ahora voy al paso uno, en cada pequeño mazo! Es decir, empiezo desde el primer paso en el primer mazo pequeño, y cuando termine ese trabajo, empiezo desde el paso uno en el siguiente mazo pequeño.

Rompo el mazo 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 confía en mí, 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 lo llamó Quick Sort. ¡Ahora, Quick Sort se acostumbra todo el tiempo!

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

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

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

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

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

Si tiene que ordenar un mazo, ¿cuál es la mejor manera? Bueno, puedes hacer lo que quieras, pero yo elegiría Quick Sort.

¿Por qué elijo Quick Sort? ¡No me gusta trabajar, por supuesto! Quiero que se haga el trabajo lo antes posible.

¿Cómo sé que Quick Sort es menos trabajo? Sé que O (n log n) es menor que O (n al cuadrado). ¡Las O son más pequeñas, por lo que Quick Sort es menos trabajo!

Ahora conoces a mi amigo, Big O. Nos ayuda a hacer menos trabajo. Y si conoces la gran O, ¡también puedes hacer menos trabajo!

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

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

[1]: Hay una manera de hacer trampa y agregar todas las cosas de uno a n, todo 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 .

Tengo una manera más simple de entender la complejidad del tiempo que la métrica más común para calcular la complejidad del tiempo es la notación Big O. Esto elimina todos los factores constantes para que el tiempo de ejecución pueda estimarse en relación con N a medida que N se aproxima al infinito. En general, puedes pensarlo 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 ciclo 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 entre 2. Esto se debe a que el algoritmo divide el área de trabajo por 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 consta de 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ítmico. Existen otras medidas de Big O como la raíz cúbica, exponencial y cuadrada, pero no son tan comunes. La notación O grande se describe como O (), donde es la medida. El algoritmo de clasificación rápida se describiría como O (N * log (N)).

Nota: Nada de esto ha tenido en cuenta las mejores, medias y peores medidas. 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 anotaciones 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: Aquí

Digamos que usted ordena 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. Desea probar qué método es más rápido. La entrega tarda casi un día en llegar y la descarga se completó unos 30 minutos antes. ¡Excelente! Entonces es una carrera apretada.

¿Qué sucede si ordeno varias películas de Blu-ray como El Señor de los Anillos, Twilight, The Dark Knight Trilogy, 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 las compras en línea, la cantidad de artículos comprados (entrada) no afecta el tiempo de entrega. La salida es constante. Llamamos a esto O (1) .

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

A partir de los experimentos, sabemos que las compras en línea escalan mejor que las descargas en línea. Es muy importante comprender 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

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 tanto como 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 compararlos cuando se habla de A y otros algoritmos, es fácil clasificar los algoritmos de acuerdo con el número de operaciones que pueden requerir (en el peor de los casos) 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 el menor número posible.

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

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

Y además

Los factores constantes son insignificantes

Si actualiza a una computadora que puede ejecutar su algoritmo el doble de rápido, la notación O grande no lo notará. Las mejoras constantes de los factores son demasiado pequeñas para ser notadas en la escala con la que funciona la notación O grande. Tenga en cuenta que esta es una parte intencional del diseño de la notación O grande.

Sin embargo, aunque se puede detectar cualquier cosa "mayor" que un factor constante.

Cuando esté interesado en realizar cálculos cuyo tamaño sea lo suficientemente "grande" como para considerarse 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 en que sé hacer que estas ideas sean rigurosas, o explicarlas si ya no son intuitivamente útiles, es enseñarte primero una notación O grande o algo similar. (aunque, una vez que comprenda bien la notación O grande en el futuro, puede valer la pena revisar estas ideas)

¿Cuál es una explicación sencilla en inglés de la notación "Big O"?

Nota muy rápida:

La O en "Big O" se refiere como "Orden" (o precisamente "orden de")
para que pueda tener su idea literalmente de que se usa para ordenar algo para compararlos.

• "Big O" hace dos cosas:

  1. Estima cuántos pasos del método aplica su computadora para realizar una tarea.
  2. ¿Facilitar el proceso de comparación con otros para determinar si es bueno o no?
  3. "Big O 'logra los dos anteriores con estandarizado Notations.

• Hay siete anotaciones más utilizadas

  1. O (1), significa que su computadora realiza una tarea con 1paso, es excelente, ordenó No.1
  2. O (logN), significa que su computadora completa una tarea con logNpasos, es buena, ordenada No.2
  3. O (N), termine una tarea con Npasos, es justo, Orden No.3
  4. O (NlogN), finaliza una tarea con O(NlogN)pasos, no es buena, Orden No.4
  5. O (N ^ 2), realiza una tarea con N^2 pasos, es malo, Orden No.5
  6. O (2 ^ N), realiza una tarea con 2^N pasos, es horrible, Orden No.6
  7. O (N!), Realiza una tarea con N!pasos, es terrible, Orden No.7

Supongamos que obtiene notación O(N^2), no solo está claro que el método toma N * N pasos para realizar una tarea, también ve que no es bueno a partir O(NlogN)de 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 usa para describir el rendimiento o la complejidad de un algoritmo.

Además, Big O establece el peor de los casos o mide los pasos del límite superior.
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.

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

Estamos tratando de ver cómo la cantidad 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, se dice que está en Big O de n.

La declaración anterior es un buen comienzo pero no del todo cierto.

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 en función de n

c = una constante

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

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

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

La ecuación se lee a medida que n se aproxima al infinito, T de n es menor o igual que c por f de n.

En la notación O grande esto se escribe como

T(n)∈O(n)

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

Volver al ingles

Según 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 Big O de n, entonces también es automáticamente el Big O de n cuadrado.

Big O de n significa que mi algoritmo se ejecuta al menos tan rápido como esto. No puede mirar la notación Big O de su algoritmo y decir que es lenta. Solo puedes decir que es rápido.

Mira esto para ver 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 de nivel de Dios) lo explica, dirás "¡Oh, eso es todo!".

Encontré una gran explicación sobre la notación O grande, especialmente para alguien que no está muy interesado en las matemáticas.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

La notación Big O se usa en informática para describir el rendimiento o la complejidad de un algoritmo. Big O describe específicamente el peor de los casos, y puede usarse para describir el tiempo de ejecución requerido o el espacio utilizado (por ejemplo, en la memoria o en el disco) por un algoritmo.

Cualquiera que haya leído Programming Pearls o cualquier otro libro de Ciencias de la Computación y no tenga una base en Matemáticas se habrá topado con una pared cuando llegue a capítulos que mencionan O (N log N) u otra sintaxis aparentemente loca. Esperemos que este artículo lo ayude a comprender los conceptos básicos de Big O y Logarithms.

Como programador primero y matemático segundo (o quizás tercero o cuarto), encontré que la mejor manera de entender Big O a fondo era producir algunos ejemplos en código. Por lo tanto, a continuación se presentan algunos órdenes comunes de crecimiento junto con descripciones y ejemplos donde sea posible.

O (1)

O (1) describe un algoritmo que siempre se ejecutará en el mismo tiempo (o espacio) independientemente del tamaño del conjunto de datos de entrada.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

EN)

O (N) describe un algoritmo cuyo rendimiento crecerá linealmente y en proporción directa al tamaño del conjunto de datos de entrada. El siguiente ejemplo también demuestra cómo Big O favorece el peor escenario de rendimiento; se podría encontrar una cadena coincidente durante cualquier iteración del bucle for y la función volvería antes, pero la notación Big O siempre asumirá el límite superior donde el algoritmo realizará el número máximo de iteraciones.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N ² )

O (N ² ) representa un algoritmo cuyo rendimiento es directamente proporcional al cuadrado del tamaño del conjunto de datos de entrada. Esto es común con algoritmos que involucran iteraciones anidadas sobre el conjunto de datos. Las iteraciones anidadas más profundas darán como resultado O (N ³ ), O (N ⁴ ), etc.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O (2 ^N )

O (2 ^N ) denota un algoritmo cuyo crecimiento se duplica con cada adición al conjunto de datos de entrada. La curva de crecimiento de una función O (2 ^N ) es exponencial: comienza muy poco profunda y luego sube meteóricamente. Un ejemplo de una función O (2 ^N ) es el cálculo recursivo de números de Fibonacci:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logaritmos

Los logaritmos son un poco más difíciles de explicar, así que usaré un ejemplo común:

La búsqueda binaria es una técnica utilizada para buscar conjuntos de datos ordenados. Funciona seleccionando el elemento central del conjunto de datos, esencialmente la mediana, y lo compara con un valor objetivo. Si los valores coinciden, devolverá el éxito. Si el valor objetivo es mayor que el valor del elemento de sonda, tomará la mitad superior del conjunto de datos y realizará la misma operación contra él. Del mismo modo, si el valor objetivo es inferior al valor del elemento de sonda, realizará la operación contra la mitad inferior. Continuará reduciendo a la mitad el conjunto de datos con cada iteración hasta que se encuentre el valor o hasta que ya no pueda dividir el conjunto de datos.

Este tipo de algoritmo se describe como O (log N). La reducción a la mitad iterativa de los conjuntos de datos descritos en el ejemplo de búsqueda binaria produce una curva de crecimiento que alcanza su punto máximo al principio y se aplana lentamente a medida que aumenta el tamaño de los conjuntos de datos, por ejemplo, un conjunto de datos de entrada que contiene 10 elementos tarda un segundo en completarse, un conjunto de datos contener 100 elementos lleva dos segundos, y un conjunto de datos que contiene 1000 elementos tomará tres segundos. Duplicar el tamaño del conjunto de datos de entrada tiene poco efecto en su crecimiento, ya que después de una sola iteración del algoritmo, el conjunto de datos se reducirá a la mitad y, por lo tanto, a la par con un conjunto de datos de entrada de la mitad del tamaño. Esto hace que los algoritmos como la búsqueda binaria sean extremadamente eficientes cuando se trata de grandes conjuntos de datos.

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, hagámoslo N y X.

Dependiendo de N y X, su algoritmo requerirá algunas operaciones, por ejemplo, en el PEOR caso 3(N^2) + log(X) operaciones.

Dado que 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 traduce 'la cantidad de operaciones que su algoritmo necesita para las peores escalas de casos con esto'.

Prefacio

algoritmo : procedimiento / fórmula para resolver un problema

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

ejemplo: se le pide a usted y a un amigo que creen una función para sumar los números del 0 al N. Se le ocurre f (x) y su amigo aparece con g (x). Ambas funciones tienen el mismo resultado, pero un algoritmo diferente. Para comparar objetivamente la eficiencia de los algoritmos, usamos 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 se vuelve arbitrariamente grande.

3 puntos clave:

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

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