¿Qué es un inglés sencillo la explicación de la "Big O" notación?

https://stackoverflow.com/questions/487258

20-08-2019
|

Pregunta

Yo preferiría que como poco la definición formal de lo posible y matemáticas simples.

Solución

Nota rápida, esto es casi ciertamente confuso La notación Big O (que es un límite superior) con la notación Theta "Q" (que es un dos-lado de la envolvente).En mi experiencia, esto es típico de los debates en la no-académico.Pedimos disculpas por cualquier confusión causada.

Big O complejidad puede ser visualizado con este gráfico:

Big O Analysis

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

Big-O la notación es un pariente de la representación de la complejidad de un algoritmo.

Hay algunos importantes y elegido deliberadamente las palabras en la frase:

relación: sólo se puede comparar manzanas con manzanas.No se puede comparar un algoritmo para hacer operaciones aritméticas de multiplicación a un algoritmo que ordena una lista de enteros.Sin embargo, una comparación de dos algoritmos para realizar operaciones aritméticas (una multiplicación, una adición) le dirá algo significativo;

representación: Big-O (en su forma más simple) reduce la comparación entre algoritmos para una sola variable.Esa variable es elegido en base a las observaciones o supuestos.Por ejemplo, los algoritmos de ordenación son, típicamente, en comparación basada en las operaciones de comparación (comparación de dos nodos para determinar su orden relativo).Esto supone que la comparación es caro.Pero, ¿y si la comparación es barato, pero el intercambio es caro?Los cambios de la comparación;y

complejidad: si me toma un segundo para ordenar 10,000 elementos cuánto tiempo me tomará para ordenar un millón?La complejidad en este caso es una medida relativa a algo más.

Volver y releer los anteriores cuando he leído el resto.

El mejor ejemplo de Big-O que puedo pensar es en hacer aritmética.Tomar dos números (123456 y 789012).Las operaciones básicas de la aritmética que hemos aprendido en la escuela fueron:

además;

resta;

la multiplicación;y

de la división.

Cada uno de estos es una operación o un problema.Un método de solución de ellos es el llamado de un algoritmo.

Además es la más sencilla.Alinear los números de arriba (a la derecha) y añadir los dígitos en una columna de escribir el último número de que, además de en el resultado.El 'decenas' parte de ese número se llega a la siguiente columna.

Supongamos que la suma de estos números es el más caro de este algoritmo.Es lógico que para agregar estos dos números juntos tenemos que sumar los 6 dígitos (y, posiblemente, llevar a un 7º).Si añadimos dos de 100 números de dos dígitos juntos tenemos que hacer 100 adiciones.Si añadimos dos 10,000 números de dos dígitos, tenemos que hacer de 10.000 adiciones.

Ver el patrón?El la complejidad (siendo el número de operaciones) es directamente proporcional al número de dígitos n en el número más grande.Llamamos a este O(n) o lineal complejidad.

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

La multiplicación es diferente.Que la línea de los números, tome el primer dígito en el número de abajo y se multiplica en turno en contra de cada dígito en el número de arriba y así sucesivamente a través de cada dígito.Así que para multiplicar dos de 6 dígitos de números debemos hacer 36 multiplicaciones.Puede que necesitemos hacer tantos como 10 o 11 de la columna suma para obtener el resultado final también.

Si tenemos dos de 100 números que necesitamos para hacer de 10.000 multiplicaciones y 200 añade.Para los dos un millón de números de un dígito necesitamos hacer un trillón de dólares (10¹²) multiplicaciones y dos millones añade.

Como el algoritmo de escalas con n-el cuadrado de la, este es O(n²) o la complejidad cuadrática.Este es un buen momento para introducir otro concepto importante:

Nosotros sólo nos preocupamos de que la parte más importante de la complejidad.

El astuto habrás dado cuenta de que podríamos expresar el número de operaciones como:n² + 2n.Pero como vimos en nuestro ejemplo con dos números de un millón de dígitos cada uno, el segundo término (2n) se convierte en insignificante (contabilidad para 0.0002% del total de las operaciones por esa etapa).

Uno puede notar que hemos asumido el peor de los casos aquí.La multiplicación de 6 dígitos de los números si uno de ellos es de 4 dígitos y el otro es de 6 dígitos, entonces sólo tenemos 24 multiplicaciones.Todavía calculamos el peor de los casos para los que la 'n', i.e cuando ambos son 6 números de un dígito.Por lo tanto Big-O notación es sobre el escenario del Peor caso de un algoritmo

El Libro De Teléfono

La siguiente mejor ejemplo que se me ocurre es el libro de teléfono, normalmente llamado las Páginas Blancas o similares, pero que va a variar de país a país.Pero estoy hablando de la que se enumeran las personas por apellido y luego las iniciales o el nombre de la primera, posiblemente dirección y, a continuación, los números de teléfono.

Ahora si estaban instruyendo a una computadora para buscar el número de teléfono para "John Smith" en un teléfono de libro que contiene 1.000.000 de nombres, ¿qué harías?Ignorando el hecho de que usted puede adivinar lo lejos, en el S de la introducción (vamos a suponer que usted no puede), ¿qué harías?

Una implementación típica podría ser la de abrir a la mitad, tomar el 500,000^th y comparar a "Smith".Si pasa a ser "Smith, John" estábamos muy afortunado.Mucho más probable es que "John Smith" será antes o después de ese nombre.Si es después, a continuación, dividir la última mitad de la libreta de teléfonos en la mitad y repite.Si es antes, a continuación, dividimos la primera mitad de la libreta de teléfonos en la mitad y repite.Y así sucesivamente.

Esto se llama un búsqueda binaria y cada día en la programación si te das cuenta o no.

Así que si quieres buscar un nombre en un libro de teléfono de un millón de nombres en realidad se puede encontrar cualquier nombre haciendo esto en más de 20 veces.En la comparación de los algoritmos de búsqueda, decidimos que esta comparación es nuestro 'n'.

Para un libro de teléfono de 3 nombres que se tarda de 2 comparaciones (en la mayoría).

Para el 7 de toma en la mayoría de los 3.

Para el 15 de toma de 4.

…

Para 1.000.000 de toma 20.

Que es asombrosamente buena ¿no?

En Big-O esto es O(log n) o logarítmica de la complejidad.Ahora el logaritmo en cuestión podría ser ln (base e), registro de₁₀, registro de₂ o alguna otra base.No importa todavía es O(log n) igual O(2n²) y O(100n² aún están tanto O(n²).

Vale la pena en este punto para explicar que Big O puede ser utilizado para determinar los tres casos con un algoritmo:

Mejor Caso: En el teléfono de la búsqueda de libros, el mejor de los casos es que nos encontramos con el nombre de una comparación.Este es O(1) o constante de la complejidad;

Esperaba Caso: Como se mencionó anteriormente este es O(log n);y

Peor De Los Casos: Esto también es O(log n).

Normalmente no nos preocupamos de el mejor de los casos.Estamos interesados en la espera y el peor de los casos.A veces, uno o el otro de estos será más importante.

De vuelta a la libreta de teléfonos.

¿Qué pasa si usted tiene un número de teléfono y quiere encontrar un nombre?La policía tiene un reverso de la libreta de teléfonos, pero tal aspecto-ups son negados para el público en general.O son ellos?Técnicamente, usted puede invertir en búsqueda de un número en un teléfono ordinario libro.Cómo?

Se comienza en el primer nombre y comparar el número.Si es un partido, grande, si no, pasar a la siguiente.Tienes que hacerlo de esta manera porque el libro de teléfono es desordenada (por el número de teléfono de todos modos).

Así que para encontrar un nombre que se da el número de teléfono de búsqueda inversa):

Mejor Caso: O(1);

Esperaba Caso: O(n) (500.000);y

Peor De Los Casos: O(n) (de 1.000.000).

El Viajante De Comercio

Este es un famoso problema en ciencias de la computación y merece una mención.En este problema se tienen N ciudades.Cada una de esas ciudades está ligado a 1 o más de los otros pueblos por un camino de una cierta distancia.El problema del Viajante es encontrar el menor recorrido que visita cada ciudad.

Suena simple?Piense de nuevo.

Si usted tiene 3 ciudades a, B y C con caminos entre todos los pares, entonces usted podría ir a:

A → B → C

A → C → B

B → C → A

B → A → C

C → A → B

C → B → A

Bueno, en realidad hay menos de que debido a que algunos de estos son equivalentes (a → B → C y C → B → a son equivalentes, por ejemplo, debido a que utilizan los mismos caminos, justo a la inversa).

En la actualidad hay 3 posibilidades.

Tome este a 4 ciudades y usted tiene (iirc) 12 posibilidades.

Con 5 es de 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⁶⁴

Así que el Big-O de que el problema del Viajante es O(n!) o factorial o de la complejidad combinatoria.

En el momento de llegar a 200 ciudades no hay tiempo suficiente en el universo para resolver el problema con los ordenadores tradicionales.

Algo en que pensar.

Polinomio Tiempo

Otro punto que me quería hacer mención rápida de es que cualquier algoritmo que tiene una complejidad de O(n^un) se dice que el polinomio de complejidad o es soluble en polinomio tiempo.

O(n), O(n²) etc.son todos polinomio tiempo.Algunos problemas no pueden ser resueltos en el tiempo polinomio.Ciertas cosas son utilizados en el mundo debido a esto. La Criptografía De Clave Pública es un buen ejemplo.Es computacionalmente difícil encontrar dos factores primos de un número muy grande.Si no, no podemos usar la clave pública de los sistemas que utilizamos.

De todos modos, eso es para mi (es de esperar que la llanura inglés) explicación de Big O (revisado).

Otros consejos

Se muestra cómo una balanza de algoritmo.

O (n ²) : conocida como complejidad cuadrática

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

Tenga en cuenta que el número de artículos aumenta por un factor de 10, pero el tiempo aumenta en un factor de 10 ². Básicamente, n = 10 y así O (n ²) nos da el factor de escala n ² que es 10 ².

O (n) : conocida como complejidad lineal

1 material: 1 segundo
10 elementos: 10 segundos
100 artículos: 100 segundos

Esta vez, el número de artículos aumenta por un factor de 10, y lo mismo ocurre con el tiempo. n = 10 y así O (n) 's factor de escala es 10.

O (1) : conocida como complejidad Constant

1 material: 1 segundo
10 artículos: 1 segundo
100 objetos: 1 segundo

El número de artículos todavía está aumentando en un factor de 10, pero el factor de escala de O (1) es siempre 1.

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

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

El número de cálculos solamente se incrementa en un registro del valor de entrada. Así pues, en este caso, suponiendo que cada cálculo toma 1 segundo, el registro de la entrada de n es el tiempo necesario, por lo tanto log n.

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

Big-O la notación (también llamado "asintótico de crecimiento" notation) es ¿qué funciones "parezca" cuando se ignoran factores constantes y cosas cerca del origen.Lo usamos para hablar de cómo la cosa escala.

Conceptos básicos

para "suficientemente" grandes entradas...

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

big-O la notación no se preocupa de factores constantes:la función 9x² se dice que "crecer exactamente igual" 10x².Tampoco big-O asintótica la notación de atención sobre no asintótica cosas ("cosas de cerca el origen" o "¿qué pasa cuando el problema es de pequeño tamaño"):la función 10x² se dice que "crecer exactamente igual" 10x² - x + 2.

¿Por qué quieres ignorar las piezas más pequeñas de la ecuación?Porque se han vuelto completamente eclipsada por los grandes partes de la ecuación, ya que consideran más grandes y de mayor escala;su contribución se convierte en empequeñecido e irrelevante.(Véase el ejemplo de la sección.)

Dicho de otra manera, es todo acerca de la relación de como vas a infinito. Si usted tiene que dividir el tiempo real que tarda el O(...), usted recibirá un factor constante en el límite de grandes entradas. Intuitivamente, esto tiene sentido:las funciones de la escala "como" uno de otro si se puede multiplicar una para la otra.Es decir, cuando decimos...

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

...esto significa que para "suficientemente grande" problema de los tamaños N (si ignoramos cosas cerca del origen), existe una constante (por ejemplo,2.5, son en su totalidad) tal que:

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

Hay muchas opciones de constante;a menudo el "mejor" elección es conocido como el "factor constante" del algoritmo...pero a menudo se ignora como hacemos caso de no más grande de términos (ver Factores Constantes de la sección de por qué en general no importa).También se puede pensar en la ecuación anterior como un límite, diciendo:"En el peor de los casos, el tiempo que se tarda nunca será peor que aproximadamente el N*log(N), dentro de un factor de 2.5 (un factor constante que no importa mucho)".

En general, O(...) es más útil, ya que a menudo la atención acerca de peor comportamiento.Si f(x) representa algo "malo" como el procesador o el uso de la memoria, a continuación,"f(x) ∈ O(upperbound)"los medios "upperbound es el peor de los casos de procesador/memoria de uso".

Aplicaciones

Como puramente construcción matemática, big-O la notación no se limita a hablar sobre el tiempo de procesamiento y la memoria.Se puede utilizar para hablar de la asymptotics de la nada donde la escala es significativo, como por ejemplo:

el número de, posiblemente, los apretones de manos entre N la gente en una fiesta (Ɵ(N²), específicamente N(N-1)/2, pero lo que importa es que "escalas como" N²)
probabilístico número esperado de personas que han visto algunas de marketing viral como una función del tiempo
sitio web de la latencia de las escalas con el número de unidades de procesamiento en la CPU o la GPU o clúster de equipo
cómo el calor de salida de las escalas en la CPU muere como una función de la cantidad de transistores, tensión, etc.
cuánto tiempo de un algoritmo debe ejecutarse, como una función del tamaño de entrada
la cantidad de espacio que un algoritmo debe ejecutarse, como una función del tamaño de entrada

Ejemplo

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

Retrocede un poco:el número de apretones de manos es exactamente n-elegir-2 o N*(N-1)/2 (cada uno de N personas sacude las manos de N-1 otras personas, pero esta doble cuenta apretones de manos para dividir por 2):

Sin embargo, para un gran número de personas, el término lineal N se empequeñece y contribuye eficazmente 0 a la relación (en el gráfico:la fracción de cajas vacías en la diagonal sobre el total de cajas, se hace más pequeña a medida que el número de participantes se hace más grande).Por lo tanto, el comportamiento de la escala es order N², o el número de apretones de manos "crece como N2".

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

Es como si las casillas de la diagonal de la tabla (N*(N-1)/2 tildes, ni siquiera existe (N² marcas de verificación asintóticamente).

(temporal digresión de "plain English":) Si quería probar esto, usted puede realizar algunas sencillas álgebra en el cociente de dividir en varios términos (lim significa "considerado en el límite de", simplemente ignoralo si no la has visto, es sólo una notación para "y N es realmente 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 'se parece a' x2 tanto para grandes valores, que si tuviéramos que escribir la relación de #apretones de manos/x2, el hecho de que no necesitamos exactamente x2 apretones de manos no aparecen en las decimal para arbitrariamente un gran rato.

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

La Construcción De La Intuición

Esto nos permite hacer declaraciones como las que...

"Por lo suficientemente grande inputsize=N, no importa lo que el factor constante es, si me doble el tamaño de entrada...

...Me doble el tiempo de O(N) ("tiempo lineal") algoritmo toma."

N → (2N) = 2(N)
...Yo el doble del cuadrado de (cuádruple), el tiempo de O(N2) ("cuadrática del tiempo") algoritmo toma." (por ejemplo,un problema 100x tan grande toma 1002=10000x el tiempo...posiblemente insostenible)

N2 → (2N)2 = 4(N2)
...Me doble-cubed (óctuple) el tiempo de O(N3) ("cúbico tiempo") algoritmo toma." (por ejemplo,un problema 100x tan grande toma 1003=1000000x el tiempo...muy insostenible)

cN3 → c(2N)3 = 8(cN3)
...Puedo añadir una cantidad fija para el momento en que un O(log(N)) ("tiempo logarítmico") algoritmo toma." (barato!)

c log(N) → c log(2N) = (c log(2))+(c log(N)) = (cantidad fija)+(c log(N))
...Yo no cambio el tiempo de una operación O(1) ("constante de tiempo") algoritmo toma." (el más barato!)

c*1 → c*1
...I "(básicamente) el doble de" el tiempo de O(N log(N)) algoritmo toma." (bastante común)

es menor que O(N^1.000001), que podría estar dispuesto a llamar básicamente lineal
...Yo ridículamente aumentar el tiempo de una O(2^N) ("tiempo exponencial") algoritmo toma." (que te haga doble (o triple, etc.) el tiempo sólo por el aumento de el problema por una sola unidad)

2^N → 2^2N = (4^N)............dicho de otra manera...... 2^N → 2^N+1 = 2^N2¹ = 2 2^N

[para los que, matemáticamente, inclinado, usted puede mouse sobre los spoilers menores sidenotes]

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

(técnicamente, el factor constante tal vez podría asunto en más esotérico ejemplos, pero he enunciado de las cosas de arriba (por ejemplo,en log(N)) de tal manera que no)

Estos son el pan y la mantequilla de pedidos de crecimiento que los programadores y computación aplicada a los científicos utilizar como puntos de referencia.Ellos ven estas todo el tiempo.(Así, mientras que técnicamente podría pensar que "la Duplicación de la entrada de hace un O(√N) del algoritmo de 1.414 veces más lento," es mejor pensar en "esto es peor que logarítmica, pero mejor que la lineal".)

Factores constantes

Generalmente no nos importa lo que la constante específica de los factores son, porque no afectan a la forma en que la función crece.Por ejemplo, dos algoritmos pueden tomar O(N) tiempo para completar, pero uno puede ser dos veces tan lento como el otro.Por lo general, no importa demasiado, a menos que el factor es muy grande, ya que la optimización es difícil de negocio ( Cuando es la optimización prematura? );también el mero hecho de escoger un algoritmo con un mejor big-O a menudo mejorar el rendimiento por órdenes de magnitud.

Algunos asintóticamente superior algoritmos (por ejemplo,un no-comparación O(N log(log(N))) ordenar) puede tener tan grande un factor constante (por ejemplo, 100000*N log(log(N))), o de arriba que es relativamente grande como O(N log(log(N))) con un oculto + 100*N, que rara vez vale la pena usar incluso en "big data".

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

O(N) los algoritmos son, en cierto sentido, el "mejor" de los algoritmos de si usted necesita leer todos los datos.El acto de la lectura un montón de datos es un O(N) operación.Cargar en memoria es generalmente O(N) (o más rápido si usted tiene soporte de hardware, o ningún tiempo en absoluto si usted ya ha leído los datos).Sin embargo, si usted toca o incluso buscar en cada pieza de datos (o incluso cada una de las otras piezas de datos), el algoritmo va a tomar O(N) tiempo para realizar esta buscando.No importa lo larga que sea la real toma de algoritmo, que será por lo menos O(N) porque pasado ese tiempo buscando en todos los datos.

Lo mismo puede decirse de la mismo acto de la escritura.Todos los algoritmos que imprima N cosas que se llevará a N de tiempo, ya que la salida es al menos ese tiempo (por ejemplo,impresión de todas las permutaciones (maneras de reorganizar) un conjunto de N jugando a las cartas es factorial: O(N!)).

Esto motiva el uso de estructuras de datos:una estructura de datos que requiere la lectura de los datos sólo una vez (generalmente O(N) tiempo), más alguna cantidad arbitraria de preprocesamiento (por ejemplo, O(N) o O(N log(N)) o O(N²)) que tratamos de mantener pequeñas.A partir de entonces, la modificación de la estructura de los datos (inserciones / deleciones / etc.) y realizar consultas sobre los datos que se toman muy poco tiempo, tales como O(1) o O(log(N)).A continuación, proceder a realizar un gran número de consultas!En general, cuanto más trabajo que usted está dispuesto a hacer antes de tiempo, al menos el trabajo que tendrás que hacer después.

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

Ingenuo método:Si usted tuvo las coordenadas de una intersección de la calle, y querían examinar las calles cercanas, usted tendría que ir a través de los millones de segmentos cada vez, y comprobar cada uno de adyacencia.
Si usted sólo necesita hacer esto una vez, no sería un problema a tener que hacer el ingenuo método de O(N) el trabajo sólo una vez, pero si quieres hacerlo muchas veces (en este caso, N veces, una vez para cada segmento), tendríamos que hacer O(N²) de trabajo, o 10000002=1000000000000 operaciones.No es bueno (un moderno equipo puede realizar cerca de un billón de operaciones por segundo).
Si utilizamos una simple estructura de una tabla hash (una instantánea de la velocidad de la tabla de búsqueda, también conocido como un hashmap o diccionario), tenemos que pagar un pequeño costo por preprocesamiento todo en O(N) tiempo.A partir de entonces, sólo toma tiempo constante, en promedio, para buscar algo por su clave (en este caso, nuestra clave es la latitud y de longitud coordenadas, redondeadas en una cuadrícula;buscamos el adyacentes gridspaces de la que sólo hay 9, que es una constante).
Nuestra tarea fue de un imposible O(N²) a un nivel manejable O(N), y todo lo que tenía que hacer era pagar un menor costo para hacer una tabla hash.
analogía:La analogía en este caso en particular es un rompecabezas de rompecabezas:Hemos creado una estructura de datos que explota una propiedad de los datos.Si nuestros segmentos de carretera son como piezas de un rompecabezas, las agrupamos por coincidencia de color y el patrón.Podemos aprovechar esto para evitar tener que hacer trabajo extra más tarde (la comparación de las piezas de un rompecabezas de color, como para cada uno de los otros, no a todos los demás de una sola pieza del rompecabezas).

La moraleja de la historia:una estructura de datos que nos permite acelerar las operaciones.Incluso estructuras de datos más avanzadas puede dejar de combinar, retraso, o incluso ignorar las operaciones en increíblemente ingeniosas maneras.Los diferentes problemas que tienen diferentes analogías, pero todos se habían implican la organización de datos en una forma que se aprovechan de alguna estructura que nos interesan, o que hemos artificialmente impuesta por la contabilidad.Nosotros hacemos el trabajo antes de tiempo (básicamente, la planificación y organización), y ahora se repite en las tareas son mucho más fácil!

Ejemplo práctico:la visualización de los pedidos de crecimiento, mientras que la codificación

Notación asintótica es, en esencia, bastante separada de la programación.Notación asintótica es un marco matemático para pensar acerca de las cosas de la escala, y puede ser utilizado en muchos campos diferentes.Que dijo...esta es la forma en que aplicar notación asintótica a la codificación.

Los conceptos básicos:Cada vez que interactuamos con cada elemento en una colección de tamaño (como una matriz, un conjunto, todas las teclas de un mapa, etc.), o realizar Una de las iteraciones de un bucle, que es un multiplcative factor de tamaño A.¿Por qué digo "un factor multiplicativo"?--porque bucles y funciones (casi por definición) han multiplicativo de tiempo de ejecución:el número de iteraciones, los tiempos de trabajo realizado en el bucle (o para las funciones de:el número de veces que se llama a la función, los tiempos de trabajo que se realiza en la función).(Esto es si no hacemos algo de fantasía, como saltar de bucles o salir del bucle antes de tiempo, o cambiar el flujo de control en la función que se basa en argumentos, lo cual es muy común.) Aquí están algunos ejemplos de las técnicas de visualización, con el acompañamiento de pseudocódigo.

(aquí, el xs representa la constante de tiempo de las unidades de trabajo, procesador de instrucciones, intérprete de instrucciones, 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, usted todavía puede ser capaz de imaginar visualmente lo que está pasando:

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í, la más reconocible de esquema puede dibujar es lo que importa;un triángulo es una de dos dimensiones de la forma (0,5 a^2), igual que un cuadrado es una forma bidimensional (A^2);el factor constante de dos, aquí se mantiene en el asintótica relación entre los dos, sin embargo, hacer caso omiso de ella como todos los factores...(Hay algunos desafortunados matices a esta técnica no voy a entrar aquí;se puede engañar a usted.)

Por supuesto, esto no significa que los bucles y funciones son malas;por el contrario, ellos son los bloques de construcción de los lenguajes de programación modernos, y les encanta.Sin embargo, podemos ver que la forma de tejido de bucles y funciones y condicionales, junto con nuestros datos (control de flujo, etc.) imita el tiempo y el espacio de uso de nuestro programa!Si el tiempo y el uso del espacio se convierte en un problema, que es cuando se recurre a la astucia, y encontrar un sencillo algoritmo o 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) puede dar un ingenuo supongo que en el peor de los casos el tiempo de ejecución.

Aquí hay otra cosa que podemos reconocer visualmente:

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

Podemos 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 quizás usted log(N) pasa de los datos, de 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

Unrelatedly pero vale la pena mencionar de nuevo:Si realizamos un hash (por ejemplo,un diccionario / hashtable de búsqueda), que es un factor de O(1).Que 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 divide y vencerás algoritmo, ~~usted puede utilizar el Maestro Teorema De (generalmente), o en el ridículo de los casos el Akra-Bazzi Teorema (casi siempre funciona)~~ buscar el tiempo de funcionamiento de su algoritmo en la Wikipedia.

Pero, los programadores no piensan como este porque, finalmente, el algoritmo de la intuición se convierte en una segunda naturaleza.Usted comenzará a código algo ineficiente, e inmediatamente pienso "estoy haciendo algo ineficiente?".Si la respuesta es "sí" Y se prevé que en realidad importan, entonces usted puede tomar un paso atrás y pensar de varios trucos para hacer que las cosas funcionen más rápido (la respuesta es casi siempre "el uso de una tabla hash", rara vez "el uso de un árbol", y muy rara vez algo un poco más complicado).

Amortizado y medio-caso de la complejidad

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

Caso Promedio:Esto no es más que el uso de big-O notación para el valor esperado de una función, en lugar de la propia función.En el caso habitual en que usted considere todas las entradas son igualmente probables, el caso promedio es sólo el promedio del tiempo de ejecución.Por ejemplo, con quicksort, aunque el peor de los casos es O(N^2) para algunas realmente malas entradas, el caso promedio es el habitual O(N log(N)) (el muy mal entradas son muy pequeñas en número, tan pocos que no nos percatamos de ellos en el caso promedio).

Amortizado En El Peor De Los Casos:Algunas estructuras de datos pueden tener un peor caso de la complejidad que es grande, pero la garantía de que si se hacen muchas de estas operaciones, el promedio de la cantidad de trabajo que haces será mejor que el peor de los casos.Por ejemplo, usted puede tener una estructura de datos que normalmente toma constante O(1) tiempo.Sin embargo, en ocasiones se 'hipo' y tomar O(N) tiempo para uno al azar de la operación, porque tal vez lo que necesita hacer algunos de la contabilidad o de la recolección de basura o algo...pero promete que si lo hace el hipo, no hipo de nuevo para N más de las operaciones.El peor de los casos el costo es aún O(N) por la operación, pero el costo amortizado a lo largo de muchos ejecuta es O(N)/N = O(1) por operación.Porque las grandes operaciones son lo suficientemente raro, la enorme cantidad de trabajos ocasionales pueden ser considerados para mezclarse con el resto de la obra como un factor constante.Podemos decir que la obra está "amortizado" más de un número suficientemente grande de las llamadas que desaparece asintóticamente.

La analogía para amortizado análisis:

Usted conduce un coche.Ocasionalmente, usted necesita pasar 10 minutos va a la estación de servicio y, a continuación, pasar 1 minuto de rellenar el tanque con gas.Si usted hace esto cada vez que iba a ninguna parte con su coche (pasan de 10 minutos en coche de la estación de gas, pasar un par de segundos de llenar un fracción de galón), sería muy ineficiente.Pero si usted llena el tanque una vez cada pocos días, el 11 minutos dedicado a la conducción de la estación de gas está "amortizado" más de un número suficientemente grande de viajes, que se puede omitir y pretender que todos sus viajes eran tal vez un 5% más.

Comparación entre promedio y amortizado en el peor de los casos:

Media-caso:Podemos hacer algunas suposiciones acerca de nuestros insumos.es decir,si nuestras entradas tienen diferentes probabilidades, nuestras salidas/tiempos de ejecución se tienen diferentes probabilidades (de la cual se toma el promedio).Generalmente asumimos que nuestros insumos son todos igualmente probable (probabilidad uniforme), pero si el mundo real, las entradas no se ajustan a nuestra hipótesis de la "media entrada", el promedio de salida/tiempo de ejecución de los cálculos puede ser sin sentido.Si usted anticipa uniformemente al azar entradas, sin embargo, esto es útil para pensar!
Amortizado en el peor de los casos:Si utiliza una amortizado en el peor de los casos la estructura de datos, el rendimiento está garantizado para estar dentro de la amortizado en el peor de los casos...con el tiempo (incluso si las entradas son elegidos por un malvado demonio que lo sabe todo y está tratando de tornillo más).Generalmente usamos esto para analizar los algoritmos que pueden ser muy "picado" en el rendimiento con el inesperado gran hipo, pero con el tiempo realizar tan bien como los otros algoritmos.(Sin embargo, a menos que su estructura de datos tiene límites superiores de mucho trabajo pendiente que está dispuesto a posponer las cosas, un mal atacante podría tal vez la fuerza para recuperar la máxima cantidad de demoraron trabajo de todos-a-la-vez.

Sin embargo, si usted está razonablemente preocupados acerca de un atacante, hay muchas otras algorítmica de los vectores de ataque que preocuparse además de la amortización y de la media de los casos.)

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

(Ver La diferencia entre el promedio de caso y análisis amortizado si está interesado en este tema.)

Multidimensional big-O

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

Toda la historia

Tenga en cuenta que el big-O no es toda la historia.Usted puede drásticamente la velocidad de algunos de los algoritmos mediante el uso de la caché, haciendo de ellos caché-ajeno, evitando los cuellos de botella mediante el trabajo con la memoria RAM, en lugar de disco, uso de paralelización, o hacer el trabajo por delante de tiempo, estas técnicas son a menudo independiente de la fin-de-crecimiento "big-O" la notación, a pesar de que usted verá a menudo el número de núcleos en el big-O la notación de los algoritmos paralelos.

También hay que tener en cuenta que debido a escondidas limitaciones de su programa, puede que no se preocupan realmente de comportamiento asintótico.Usted puede estar trabajando con un acotado número de valores, por ejemplo:

Si usted está ordenando algo así como 5 elementos, usted no desea utilizar el speedy O(N log(N)) quicksort;usted desea utilizar ordenación por inserción, que pasa a funcionar bien en pequeñas entradas.Estas situaciones a menudo viene en dividir y conquistar algoritmos, donde se puede dividir el problema en partes más y más pequeñas subproblemas, como recursiva de clasificación, transformada rápida de Fourier, o la multiplicación de la matriz.
Si algunos de los valores de eficacia limitada debido a escondidas hecho (por ejemplo,el promedio de nombre humano es suavemente limitada en unas 40 cartas, y la edad humana, suavemente delimitada en torno a los 150).Usted también puede imponer límites en su entrada para realizar eficazmente términos constantes.

En la práctica, incluso entre los algoritmos que tienen las mismas o similares de rendimiento asintótica, su mérito relativo en realidad puede ser impulsada por otras cosas, como por ejemplo:otros factores de rendimiento (quicksort y mergesort son tanto O(N log(N)), pero quicksort toma ventaja de los cachés de la CPU);no consideraciones de rendimiento, como la facilidad de aplicación;si la biblioteca está disponible, y cómo de buena reputación y mantenimiento de la biblioteca.

Los programas también se ejecutará más lento en un 500MHz equipo vs 2GHz equipo.No podemos considerar esto como parte de los recursos de los límites, porque pensamos de la escala en términos de los recursos de máquina (por ejemplo,por ciclo de reloj), no por real segunda.Sin embargo, hay cosas similares que se pueden 'secreto' afectar al rendimiento, tales como la de si se está ejecutando bajo emulación, o si el compilador de código optimizado o no.Estos pueden realizar algunas operaciones básicas toma más tiempo (incluso en relación con cada uno de los otros), o incluso acelerar o ralentizar algunas operaciones asintóticamente (incluso con respecto a otro).El efecto puede ser pequeña o grande entre los diferentes implementación y/o el medio ambiente.¿Cambiar de idioma o de las máquinas, para ganarse ese poco de trabajo extra?Que depende de un centenar de otras razones (necesidad, habilidades, compañeros de trabajo, la productividad de los programadores, el valor monetario de su tiempo, la familiaridad, soluciones, ¿por qué no de la asamblea o de la GPU, etc...), que pueden ser más importantes que el rendimiento.

De los temas anteriores, como lenguaje de programación, casi nunca son considerados como parte del factor constante (ni deben);sin embargo, uno debe ser consciente de ellos, porque a veces (aunque raramente) que pueden afectar a las cosas.Por ejemplo, en cpython, el nativo de la cola de prioridad de aplicación es asintóticamente no es la óptima (O(log(N)) en lugar de O(1) para su elección de la inserción o de encontrar-min);¿utilizas otra aplicación?Probablemente no, ya que la implementación de C es probablemente más rápido, y probablemente hay otros problemas similares en otros lugares.Hay ventajas y desventajas;a veces son importantes y a veces no.

(editar:El "plain English" explicación termina aquí.)

Matemáticas anexos

La integridad, la definición precisa de los grandes-O la notación es la siguiente: f(x) ∈ O(g(x)) significa que el f "es asintóticamente superior delimitada por la const*g":ignorando todo lo que a continuación algunos finito valor de x, existe una constante tal que |f(x)| ≤ const * |g(x)|.(Los otros símbolos son como sigue:como O significa ≤, Ω significa ≥.Hay minúsculas variantes: o significa <y ω los medios >.) f(x) ∈ Ɵ(g(x)) significa tanto f(x) ∈ O(g(x)) y f(x) ∈ Ω(g(x)) (superior e inferior delimitada por g):existen algunas constantes tales que f siempre va a estar en la "banda" entre const1*g(x) y const2*g(x).Es la más fuerte asintótica declaración que usted puede hacer y más o menos equivalente a ==.(Lo siento, he elegido para retrasar la mención de los valores absolutos de los símbolos hasta ahora, en aras de la claridad;sobre todo porque nunca he visto que los valores negativos se presentan en una ciencia de la computación contexto).

Las personas a menudo utilizan = O(...), que es quizás el más correcto de los comp de la sci' la notación, y totalmente legítimo de usar;"f = O (...)", se lee "f es de orden .../ f es xxx-delimitada por ..." y se considera como "f es una expresión cuyo asymptotics son ...".Me enseñó a usar el más riguroso ∈ O(...). ∈ significa "es un elemento de" (leer como antes). O(N²) en realidad es un la equivalencia de la clase, es decir, es un conjunto de cosas que consideramos ser el mismo.En este caso en 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.El = la notación puede ser el más común, y se utiliza incluso en los periódicos de renombre mundial de equipo de científicos.Además, es a menudo el caso de que en un ambiente informal, la gente va a decir O(...) cuando quieren decir Ɵ(...);esto es técnicamente cierto, ya que el conjunto de las cosas Ɵ(exactlyThis) es un subconjunto de O(noGreaterThanThis)...y es más fácil de escribir.;-)

EDIT: Nota rápida, esto es casi seguro confuso notación Big O (que es un límite superior unido) con la notación Theta (que es tanto un límite superior e inferior). En mi experiencia, esto es en realidad típica de los debates en ámbitos no académicos. Disculpas por cualquier confusión causada.

En una frase:? A medida que el tamaño de su trabajo aumenta, cuánto tiempo más se tarda en completarla

Es evidente que sólo está usando el "tamaño" como la entrada y "tiempo necesario" como la salida -. La misma idea se aplica si usted quiere hablar de uso de la memoria, etc.

Este es un ejemplo donde tenemos N camisetas que queremos que se seque. Vamos a suponemos 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 ...

El uso de una línea de lavado exterior: suponiendo que tiene un patio trasero infinitamente grande, el lavado se seca en O (1) tiempo. Por más que se tiene de ella, que va a obtener el mismo sol y el aire fresco, por lo que el tamaño no afecta el tiempo de secado.
El uso de un secador de tambor: pones 10 camisas en cada carga, y luego que haya terminado una hora más tarde. (No haga caso de los números reales aquí -. Que son irrelevantes). Así secado 50 camisas toma sobre 5 veces más que las de secado 10 camisas
Poner todo en un armario al aire: Si ponemos todo en una gran pila y dejar que el calor en general hazlo, que tomará mucho tiempo para que las camisas medio para conseguir seco. No me gustaría que adivinar el detalle, 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 decir qué algoritmo será más rápido para un determinado tamaño. Tome una tabla hash (clave de cadena, el valor de número entero) vs un array de pares (cadena, entero). ¿Es más rápido para encontrar una llave en la tabla hash o un elemento de la matriz, sobre la base de una cadena? (Es decir, para la matriz, "encontrar el primer elemento en la parte cadena coincide con la clave dada.") Hashtables generalmente se amortizan (~ = "en promedio") O (1) - una vez que se establecieron, se debe tomar alrededor al mismo tiempo para encontrar una entrada en una tabla 100 de entrada como en una mesa 1000000 entrada. Encontrar un elemento de una matriz (basado en el contenido en lugar de índice) es lineal, es decir, O (N) -. En promedio, vas a tener que mirar a la mitad de las entradas

¿Esto hace que una tabla hash más rápido que una matriz para las búsquedas? No necesariamente. Si usted tiene una muy pequeña colección de entradas, una matriz puede así ser más rápido - usted puede ser capaz de comprobar todas las cadenas en el momento en que se necesita para simplemente calcular el código hash de la que usted está mirando. A medida que el conjunto de datos se hace más grande, sin embargo, la tabla hash finalmente 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 hacen grandes.

Ejemplos:

O (n): Si el doble del tamaño de entrada los dobles de tiempo de ejecución
O (n ²): Si el tamaño de entrada duplica el tiempo de ejecución se cuadruplica
O (log n): Si el tamaño de entrada duplica los incrementos de tiempo de ejecución por uno
O (2 ⁿ): Si el tamaño de entrada se incrementa en uno, los dobles de tiempo de ejecución

El tamaño de entrada es generalmente el espacio en bits necesarios para representar la entrada.

notación Big O es más comúnmente utilizado por los programadores como una medida aproximada de cuánto tiempo un cálculo (algoritmo) tomará para completar expresado como una función del tamaño de la conjunto de entrada.

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

Más precisamente Big O notación se utiliza para expresar el comportamiento asintótico de una función. Eso significa cómo la función se comporta como lo tiende a infinito.

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

O (1) - tiempo para completar es la misma, independientemente del tamaño de conjunto de entrada. Un ejemplo está accediendo a un elemento de matriz por el índice.
O (log n) - Tiempo para completar aumenta aproximadamente en línea con el log2 (n). Por ejemplo 1024 artículos se llevan a aproximadamente dos veces tan largo como 32 elementos, porque Log2 (1024) = 10 y Log2 (32) = 5. Un ejemplo es encontrar un elemento en un binario árbol de búsqueda (BST).
O (N) - Tiempo para completar que escala linealmente con el tamaño de la conjunto de entrada. En otras palabras, si se duplica el número de elementos en el conjunto de entrada, el algoritmo tiene más o menos el doble de tiempo. Un ejemplo es contar el número de elementos de una lista enlazada.
O (N log N) - tiempo para completar aumenta por el número de artículos veces el resultado de Log2 (N). Un ejemplo de esto es pila de clasificación y rápida tipo .
O (N ^ 2) - tiempo para completar es aproximadamente igual al cuadrado del número de elementos. Un ejemplo de esto es tipo .
O (N!) - tiempo para completar es el factorial del conjunto de entrada. Un ejemplo de esto es la viajar problema del vendedor solución de fuerza bruta .

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

Big O es sólo una forma "Express" a sí mismo en una forma común, "¿cuánto tiempo / espacio se tarda en ejecutar mi código?".

Usted puede ver a menudo a O(n), O(n²), O(nlogn), y así sucesivamente, todas estas son formas de mostrar,¿Cómo funciona un algoritmo de cambio?

O(n) significa Grande O es n, y ahora usted podría pensar, "¿Qué es n!?" Así "n" es la cantidad de elementos.Imágenes que desea buscar un Elemento en una Matriz.Usted tendría que mirar en Cada elemento y como "el elemento correcto/item?" en el peor de los casos, el elemento está en el último índice, lo que significa que se tomó todo el tiempo, ya que hay elementos en la lista, de manera genérica, podemos decir "oh, hey, n es una feria determinada cantidad de valores!".

Así que usted puede entender lo que "n²"significa, pero para ser más específicos, juegan con la idea de que haya una simple, la simplicidad de los algoritmos de ordenación;bubblesort.Este algoritmo necesita para mirar a través de la totalidad de la lista para cada elemento.

Mi lista

El flujo de aquí sería:

Comparar 1 y 6, que es el más grande?Ok 6 está en la posición correcta, de avanzar!
Comparar 6 y 3, oh, 3 es menor!Vamos a mover eso, Aceptar la lista cambiado, tenemos que empezar desde el principio ahora!

Esto es O n² porque, usted necesita para buscar en todos los elementos de la lista hay "n" elementos.Para cada elemento, se mira en todos los elementos, una vez más, para comparar, esta también es una "n", de modo que para cada elemento, se mira "n" veces el significado de n*n = n²

Espero que esto es tan simple como usted lo desea.

Pero recuerde, Big O es sólo una manera de experss a sí mismo en la forma del tiempo y del espacio.

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

Hay una gran cantidad de información que Big O no le dice acerca de un algoritmo dado. Se corta hasta el hueso y sólo da información sobre la naturaleza de escala de un algoritmo, específicamente cómo el uso de los recursos (tiempo de reflexión o de la memoria) de un algoritmo de escalas en respuesta al "tamaño de entrada".

Tenga en cuenta la diferencia entre una máquina de vapor y un cohete. Ellos no son más que diferentes variedades de una misma cosa (como, por ejemplo, un motor de Prius vs un motor de Lamborghini) pero son drásticamente diferentes tipos de sistemas de propulsión, en su núcleo. Una máquina de vapor puede ser más rápido que un cohete de juguete, pero sin motor de pistón de vapor será capaz de alcanzar la velocidad de un vehículo de lanzamiento orbital. Esto es porque estos sistemas tienen diferentes características de escala con respecto a la relación de combustible requerido ( "uso de recursos") para llegar a una velocidad dada ( "tamaño de entrada").

¿Por qué es esto tan importante? Debido a ofertas de software con problemas que pueden diferir en tamaño por factores de hasta un billón de dólares. Tengamos en cuenta que por un momento. La relación entre la velocidad necesaria para viajar a la Luna y la velocidad de la marcha humana es menos de 10.000: 1, y que es absolutamente pequeña en comparación con el rango de entrada de los tamaños de software puede hacer frente. Y debido a que el software puede hacer frente a una gama de entrada astronómico en el tamaño existe la posibilidad de que la complejidad O grande de un algoritmo, es la naturaleza fundamental de escala, para superar a los detalles de implementación.

Considere el ejemplo de clasificación canónica. Bubble-tipo es O (n ²) mientras merge-tipo es O (n log n). Digamos que usted tiene dos aplicaciones de clasificación, la aplicación A, que utiliza la burbuja-tipo y la aplicación B que utiliza Fusionar-tipo, y digamos que para los tamaños de entrada de alrededor de 30 elementos de aplicación A es 1.000 x más rápido que la aplicación B en la clasificación. Si usted nunca tiene que especie mucho más de 30 elementos, entonces es obvio que se debe preferir la aplicación A, ya que es mucho más rápido en estos tamaños de entrada. Sin embargo, si usted encuentra que usted puede tener que ordenar diez millones de artículos a continuación, lo que se espera es que la aplicación B en realidad termina siendo miles de veces más rápido que la aplicación A en este caso, en su totalidad debido a la forma en que cada algoritmo escalas.

Aquí está la llanura Inglés bestiario que tienden a utilizar la hora de explicar las variedades comunes de Big-O

En todos los casos, prefieren algoritmos más arriba en la lista de los más bajos en la lista. Sin embargo, el coste de mover a una clase de complejidad más caro varía de forma significativa.

O (1):

No hay crecimiento. Independientemente de lo grande que es el problema, se puede resolver en la misma cantidad de tiempo. Esto es algo análogo a la radiodifusión donde toma la misma cantidad de energía para transmitir sobre una distancia dada, independientemente de la cantidad de personas que se encuentran dentro del alcance de radiodifusión.

O (log n ):

Esta complejidad es lo mismo que O (1) , excepto que es sólo un poco peor. Para todos los efectos prácticos, se puede considerar esto como un muy gran escala constante. La diferencia en el trabajo de procesamiento entre 1 mil y 1 mil millones de artículos es sólo un factor de seis.

O ( n ):

El costo de la solución del problema es proporcional a la magnitud del problema. Si su problema se duplica en tamaño, entonces el costo de la solución se duplica. Dado que la mayoría de los problemas tienen que ser escaneada en el ordenador de alguna manera, como la entrada de datos, lecturas de disco, o el tráfico de red, esto es generalmente un factor de escala asequible.

O ( n log n ):

Esta complejidad es muy similar a O ( n ) . Para todos los propósitos prácticos, los dos son equivalentes. Este nivel de complejidad en general, todavía sería considerado escalable. Al ajustar supuestos algunos O ( n log n ) algoritmos pueden ser transformados en O ( n ) algoritmos. Por ejemplo, que limita 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 como el "efecto red", donde todo el mundo en una red podría saber todos los demás en la red. El crecimiento es caro. La mayoría de las soluciones escalables no pueden utilizar algoritmos con este nivel de complejidad sin hacer gimnasia significativos. Esto se aplica generalmente a todas las otras complejidades polinómicas - O ( n ^k) -., Así

O (2 ⁿ):

no escala. Usted no tiene ninguna esperanza de resolver cualquier problema no trivial de tamaño. Útil para saber lo que debe evitar, y para los expertos para encontrar algoritmos aproximados que están en O ( n ^k) .

Big O es una medida de cuánto tiempo / espacio un algoritmo utiliza 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 como su entrada.

Si un algoritmo es O (n ²), entonces el aumento de tiempo / espacio a razón de su entrada al cuadrado.

y así sucesivamente.

Es muy difícil medir la velocidad de los programas de software, y cuando tratamos, las respuestas pueden ser muy compleja y llena de excepciones y casos especiales. Este es un gran problema, porque todas esas excepciones y casos especiales son una distracción y poco útil cuando queremos comparar dos programas diferentes entre sí para saber qué es "más rápido".

Como resultado de toda esta complejidad inútil, la gente trata de describir la velocidad de los programas de software utilizando las expresiones más pequeñas y menos complejas (matemáticos) posible. Estas expresiones son aproximaciones muy, muy crudo:. Aunque, con un poco de suerte, van a captar la "esencia" de si una pieza de 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 cree erróneamente que la expresión es de ninguna manera precisa).

Si usted lee el "Oh" en el sentido de "en el orden de" o "aproximadamente" no te equivocarás. (Creo que la elección de la Big-Oh podría haber sido un intento de humor).

Lo único que estas expresiones "Big-Oh" tratan de hacer es describir lo mucho que el software se ralentiza a medida que aumenta la cantidad de datos que el software tiene que procesar. Si duplicamos la cantidad de datos que necesita ser procesada, no el software necesario el doble de tiempo para terminar su trabajo? Diez veces más largo? En la práctica, hay un número muy limitado de grandes-OH expresiones que se encontrará y la necesidad de preocuparse por:

Lo bueno:

O(1) Constante . El programa toma el mismo tiempo para correr, no importa lo grande que es la entrada
O(log n) logarítmica . El programa de tiempo de ejecución aumenta sólo lentamente, incluso con grandes aumentos en el tamaño de la entrada

Lo malo:

O(n) Linear :. El programa de tiempo de ejecución aumenta proporcionalmente con el tamaño de la entrada
O(n^k) Polynomial : -. El tiempo de procesamiento crece más y más rápido - como una función polinómica - como el tamaño de los aumentos de entrada

... y lo feo:

O(k^n) exponencial El programa de gestión de tiempo aumenta muy rápidamente con incluso un aumento moderado en el tamaño del problema -. Sólo es práctico para procesar pequeños conjuntos de datos con algoritmos exponenciales
O(n!) factorial El programa en tiempo de ejecución será más larga de lo que puede permitirse el lujo de esperar a nada más que los conjuntos de datos muy pequeños y más triviales de apariencia.

¿Qué es una explicación sencilla del Inglés O grande? Con tan poco definición formal como las matemáticas posible y sencilla.

Una Explicación Inglés Simple de la Necesidad para Big-O Notación:

Cuando programamos, estamos tratando de resolver un problema. Lo que se llama código de un algoritmo. notación Big O nos permite comparar el rendimiento peor de los casos de nuestros algoritmos de una manera estandarizada. especificaciones de hardware varían con el tiempo y las mejoras en el hardware pueden reducir el tiempo que tarda un algoritmos para funcionar. Pero reemplazando el hardware no significa que nuestro algoritmo es mejor o mejorado con el tiempo, como nuestro algoritmo sigue siendo el mismo. Así pues, para que nos permita comparar diferentes algoritmos, para determinar si uno es mejor o no, utilizamos la notación O grande.

Una Explicación Inglés Simple de ¿Cuál Big O notación es:

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

Una simple respuesta directa puede ser:

O grande 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 2cents.

Big-O, es tasa de aumento de recurso consumido por el programa, w.r.t. problema instancia de tamaño

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

dicen que el problema es "encontrar 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-instance-size = 3, iteraciones-en-loop = 3

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

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

dicen que el problema es "encontrar 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-instance-size = 3, Total-iteraciones = 3 * 3 = 9

problema instancia = {5,10,15,20,25} ==> problema-instance-size = 5, Total-iteraciones = 5 * 5 = 25

Para la entrada de tamaño "n" el programa está creciendo a una velocidad de iteraciones "n * n" en array. 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 de tiempo de ejecución.El n es el número de elementos en el problema (me.e tamaño de una matriz, el número de nodos en un árbol, etc.) Estamos interesados en describir el tiempo de ejecución como n crece.

Cuando se dice que algunos algoritmo es O(f(n)), estamos diciendo que el tiempo (o espacio) por el algoritmo es siempre inferior a la de algunas constantes veces 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 la que siempre será mayor que el tiempo de ejecución de binarios de búsqueda.En este caso, usted siempre tendrá algún factor constante de log(n) comparaciones.

En otras palabras, donde g(n) es el tiempo de funcionamiento 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 de las constantes.

" ¿Qué es una explicación sencilla del Inglés Big O? Con tan poco formal definición matemática como sea posible y sencilla. "

Tal pregunta muy simple y corto parece al menos para merecer una respuesta igual de corto, como un estudiante puede recibir durante la tutoría.

notación Big O simplemente le dice cuánto tiempo * un algoritmo puede ejecutarse dentro, en términos de sólo la cantidad de datos de entrada **.

(* en un sentido maravilloso, -unidad libre de tiempo!)
(** que es lo que importa, porque la gente va siempre quieren más , ya sea que vivan hoy o mañana)

Bueno, lo que es tan maravilloso de la notación O grande si eso es lo que hace?

En la práctica, el análisis de Big O es tan útil e importante porque Big O pone el foco en ángulo recto en propia complejidad del algoritmo y completamente ignora cualquier cosa que no es más que una constante de proporcionalidad, como un motor de JavaScript, la velocidad de una CPU, la conexión a Internet, y todas esas cosas que se convierten rápidamente llegar a ser tan ridículamente anticuada como un modelo T . O grande se centra en el rendimiento sólo en la forma en que importa igualmente tanto a las personas que viven en el presente o en el futuro.
notación Big O también arroja luz directamente sobre el principio más importante de la programación informática / ingeniería, el hecho de que inspira todos los buenos programadores para seguir pensando y soñando: la única manera de lograr resultados más allá de la marcha lenta hacia adelante de la tecnología es inventar un mejor algoritmo .

Algoritmo de ejemplo (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;
}

Algoritmo descripción:

Este algoritmo de búsqueda en una lista, elemento por elemento, buscando una clave,
Iterar sobre cada elemento de la lista, si es la clave, a continuación, devolver True,
Si el bucle ha terminado sin encontrar la clave, devuelve False.

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

Para encontrar El Big-O en el Tiempo de la Complejidad:

Calcular cuánto tiempo (en cuanto a tamaño de entrada) el peor de los casos se lleva a:
Peor De Los Casos:la clave no existe en la lista.
Tiempo(el Peor Caso) = 4n+1
Tiempo:O(4n+1) = O(n) | en Big-O, las constantes son descuidados
O(n) ~ Lineal

También hay Grandes-Omega, que representan la complejidad de el Mejor de los Casos:

El Mejor De Los Casos:la clave es el primer elemento.
Tiempo(El Mejor De Los Casos) = 4
Tiempo:Ω(4) = O(1) ~ Instant\Constante

Big O

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

f (x) = k (x) g (x)
k está limitada en alguna vecindad de un (si a = + ∞, esto significa que hay un número N y M tal que para cada x> N, | k (x) |

En otras palabras, en la llanura Inglés: f (x) = O ( g (x)), x → a, significa que en un entorno de un, f descompone en el producto de g y algunos función acotada.

Pequeño O

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

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

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

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 "=" utiliza un "igualdad falso": es cierto que O (g (x)) = O (g (x)), pero falsa que O (g (x)) = o (g (x)). Del mismo modo, es aceptable para escribir "ln (x) = O (x) cuando x → + ∞", pero la fórmula "o (x) = ln (x)" no tendría ningún sentido.

Más ejemplos

O (1) = O (n) = O (n ²) cuando n → + ∞ (pero no a la inversa, la igualdad es "falso"),
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

notación Big O es una forma de describir la rapidez con que un algoritmo se ejecutará dado un número arbitrario de parámetros de entrada, que llamaremos "n". Es útil en la informática debido a que diferentes máquinas funcionan a diferentes velocidades, y simplemente decir que un algoritmo tarda 5 segundos no le dice mucho, porque si bien puede estar ejecutando un sistema con un procesador octo-core 4.5 GHz, que pueden estar ejecutándose a 15 años de edad, de sistema de 800 MHz, lo que podría llevar más tiempo, independientemente del algoritmo. Así que en lugar de especificar la rapidez con un algoritmo se ejecuta en términos de tiempo, decimos que la rapidez con que se ejecuta en cuanto a número de parámetros de entrada, o "n". Al describir los algoritmos de esta manera, somos capaces de comparar las velocidades de algoritmos sin tener que tener en cuenta la velocidad de la computadora en sí misma.

No estoy seguro de que estoy contribuyendo aún más al sujeto, pero todavía pensaba que me gustaría compartir: Una vez encontré esta entrada de blog tener algunos bastante útil (aunque muy básico) explicaciones y ejemplos sobre Big O:

A través de ejemplos, esto ayudó a que los fundamentos pelados en mi cráneo de tortuga-como, por lo que creo que es un bonito descenso de leer para que te va en la dirección correcta 10 minutos.

Quieres saber todo lo que hay que saber de O grande?Así que yo también.

Así que para hablar de big O, voy a utilizar las palabras que tienen un solo golpe en ellos.Un sonido por palabra.Pequeñas palabras son rápidos.Usted sabe estas palabras, y yo también.Vamos a utilizar palabras con un sonido.Son pequeños.Estoy seguro de que usted sabe todo de las palabras que vamos a utilizar!

Ahora, vamos tú y yo a hablar de trabajo.La mayoría del tiempo, no me gusta trabajar.¿Te gusta trabajar?Puede ser el caso de que usted, pero yo estoy seguro de que no.

No me gusta para ir a trabajar.No me gusta pasar tiempo en el trabajo.Si yo tuviera a mi manera, me gustaría simplemente para jugar y hacer cosas divertidas.¿Sientes lo mismo como puedo hacer?

Ahora, a veces, tengo que ir a trabajar.Es triste, pero cierto.Así que, cuando estoy en el trabajo, tengo una regla:Yo trate de hacer menos trabajo.Tan cerca sin trabajar como puedo.Luego me voy a jugar!

Así que aquí está la gran noticia:el big O me puede ayudar no para hacer el trabajo!Puedo jugar más de las veces, si sé big O.Menos trabajo, más jugar!Eso es lo grande O me ayuda a hacer.

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

Wow, no me gusta trabajar.Pero bueno, tengo que hacer esto.Así que aquí voy.

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

Así que vamos a no hacer el trabajo.Vamos tú y yo solo pienso en lo difícil que es.La cantidad de trabajo que tengo que hacer, para agregar seis números?

Bien, vamos a ver.Debo añadir uno y dos, y a continuación, añadir a tres, y a continuación, añadir a cuatro... en definitiva, que el recuento de seis añade.Tengo que hacer seis añade a resolver esto.

Aquí viene big O, para que nos digan sólo lo difícil que esta la matemática es.

Big O, dice:debemos hacer seis añade a resolver esto.Un complemento, para cada cosa, de uno a seis.Seis pequeños trozos de trabajo...cada uno de los bits de trabajo es un complemento.

Bueno, no voy a hacer el trabajo para que lo agregue ahora.Pero yo sé lo difícil que sería.Serían seis, añade.

Oh, no, ahora tengo más trabajo.Sheesh.Que hace que este tipo de cosas?!

Ahora me piden que añadir de uno a diez!Por qué iba yo a hacer eso?Yo no quiero agregar uno a seis.Para agregar de uno a diez... bueno... que sería aún más difícil!

Cuánto más difícil sería?De todo el trabajo que tengo que hacer?Necesito más o menos los pasos?

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

No quiero agregar ahora.Sólo quiero pensar en lo difícil que podría ser para agregar que mucho.Y, espero que, para jugar tan pronto como puedo.

Agregar de uno a seis años, que es algo de trabajo.Pero, ¿se puede ver, agregar de uno a diez, que es más trabajo?

Big O es su amigo y la mía.Big O, nos ayuda a pensar en la cantidad de trabajo que tenemos que hacer, así que se puede planificar.Y, si somos amigos con big O, él nos puede ayudar a elegir el trabajo que no es tan difícil!

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

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

Espera!¿Qué es el n?No me olvido de que?¿Cómo puedo agregar de una a n si no me dices lo que n es?

Bueno, no sé lo que n es.No se me dijo.Estaban?No?Oh, bueno.Por lo que no puede hacer el trabajo.¡Uf.

Pero si bien no podemos hacer el trabajo ahora, podemos adivinar que tan difícil sería que, si supiéramos n.Habría que añadir n las cosas, ¿verdad?Por supuesto!

Ahora aquí viene O grande, y él nos dirá cuán difícil es esta obra.Él dice:para agregar todas las cosas de uno a N, uno por uno, es O(n).Para agregar todas estas cosas, [sé que debo agregar a n veces.][1] Que es grande O!Él nos dice lo difícil que es hacer algún tipo de trabajo.

Para mí, creo que de grande O como un grande, lento, jefe hombre.Él piensa en el trabajo, pero no lo hace.Él puede decir, "Que el trabajo es rápido." O, se podría decir, "Que el trabajo es lento y duro!" Pero no hacer el trabajo.Sólo se ve en el trabajo, y luego nos dice cuánto tiempo podría tomar.

Me importa mucho para la gran O.Por qué?No me gusta trabajar!A nadie le gusta trabajar.Es por eso que a todos nos gusta O grande!Él nos dice cómo de rápido que podemos trabajar.Él nos ayuda a pensar de cómo es trabajar duro.

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

Nos dieron una cubierta de diez tarjetas.Están todos mezclados:siete, cuatro, dos, seis... no directamente en todo.Y ahora...nuestro trabajo es para ordenarlas.

Ergh.Eso suena como un montón de trabajo!

¿Cómo podemos resolver esto de la cubierta?Tengo un plan.

Voy a mirar cada par de tarjetas, pareja por pareja, a través de la cubierta, desde el primero al último.Si la primera tarjeta en una pareja es grande y la siguiente carta en la que par es pequeña, yo intercambiarlos.Otra cosa, puedo ir a la siguiente pareja, y así sucesivamente y así sucesivamente...y de pronto, la cubierta se hace.

Cuando la cubierta está hecho, me pregunto:¿puedo intercambiar tarjetas en que pase?Si es así, debo hacer todo de nuevo, desde la parte superior.

En algún punto, en algún momento, no habrá swaps, y nuestra especie de la cubierta a cabo.Mucho trabajo!

Así, la cantidad de trabajo que tendría que ser, para ordenar las tarjetas con esas reglas?

Tengo diez tarjetas.Y, la mayoría del tiempo, es decir, si yo no tengo un montón de suerte-tengo que ir a través de toda la baraja hasta diez veces, con hasta diez tarjeta de swaps de cada momento a través de la cubierta.

Big O, ayúdame!

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

¿Por qué lo dice n al cuadrado?

Bien, usted sabe n al cuadrado es n veces n.Ahora, me sale esto:n tarjetas marcada, hasta lo que podría ser n veces a través de la cubierta.Que es de dos bucles, cada uno con n pasos.Que es n el cuadrado de la cantidad de trabajo por hacer.Un montón de trabajo, seguro!

Ahora, cuando big O dice que va a tomar O(n al cuadrado) de trabajo, no significa n al cuadrado añade, en la nariz.Podría haber algunas pequeñas poco menos, para algunos casos.Pero en el peor de los casos, estará cerca de n al cuadrado pasos de trabajo para ordenar la baraja.

Ahora aquí es donde los grandes O es nuestro amigo.

Big O señala esto:como n se vuelve grande, cuando nos ordenar las cartas, el trabajo se vuelve MUCHO MÁS DIFÍCIL que el anterior solo agregar-estas-cosas de trabajo.¿Cómo sabemos esto?

Así, si n toma los verdaderos grandes, no nos importa lo que podríamos añadir a n o n al cuadrado.

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

Big O, nos dice que para arreglar las cosas es más difícil que para añadir cosas.O(n al cuadrado) es más de O(n) para las grandes n.Lo que significa:si n toma los verdaderos grandes, para ordenar un sistema mixto de cubierta de n cosas DEBEN tomar más tiempo, que acaba de agregar n mezclado cosas.

Big O no resolver el trabajo por nosotros.Big O, nos dice cómo de duro es el trabajo.

Tengo una baraja de cartas.Me hizo algo de ellos.Usted ayudó.Gracias.

Hay una más rápida manera de ordenar las tarjetas?Puede O grande ayudarnos?

Sí, hay una más rápida manera!Se necesita algún tiempo para aprender, pero funciona...y funciona bastante rápido.Puedes intentarlo demasiado, pero tómese su tiempo con cada paso y no perder su lugar.

En esta nueva forma de ordenar una baraja, no podemos comprobar los pares de tarjetas de la manera que lo hicimos hace un tiempo.Aquí están las nuevas reglas para ordenar este deck:

Uno:Puedo elegir una tarjeta en la parte de la cubierta que trabajamos ahora.Usted puede elegir uno para mí, si te gusta.(La primera vez que hacemos esto, "la parte de la cubierta que trabajamos en el ahora" es el conjunto de la cubierta, por supuesto).

Dos:Yo separación de la cubierta de la tarjeta que usted eligió.¿Qué es esta separación;¿cómo puedo separación?Bueno, me voy de la tarjeta de inicio, uno por uno, y me busque una tarjeta que es más alta que la separación de la tarjeta.

Tres:Voy desde el final de la tarjeta, y me busque una tarjeta que es más baja que la separación de la tarjeta.

Una vez que he encontrado en estas dos cartas, me swap de ellos, y se vaya a buscar más tarjetas para intercambiar.Es decir, puedo volver al paso Dos, y la separación en la tarjeta que usted escogió a algunos más.

En algún punto, este bucle (de Dos a Tres) va a terminar.Se termina cuando las dos mitades de esta búsqueda se reúnen en la separación de la tarjeta.Entonces, acabamos de deformaciones de la cubierta con la tarjeta que usted eligió en el paso Uno.Ahora, todas las cartas cerca del inicio son más bajos que la separación de la tarjeta;y las cartas cerca del final más alto de la separación de la tarjeta.Truco!

Cuatro (y esta es la parte divertida):Tengo dos pequeñas cubiertas de ahora, uno de los más bajos de la separación de la tarjeta, y uno más alto.Ahora me vaya al paso uno, en cada uno de los pequeños de la cubierta!Es decir, puedo empezar desde el paso Uno en la primera cubierta, y cuando ese trabajo está hecho, empezar desde el paso Uno en el lado pequeño de la cubierta.

Yo romper la baraja en partes, y ordenar cada parte, más pequeño y más pequeño, 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 todo.Es mucho menos trabajo que la primera forma de ordenar las cosas!

¿Qué es este tipo se llama?Se llama Quick Sort!Ese tipo fue hecho por un hombre llamado C.A.R.Hoare y la llamó Ordenación Rápida.Ahora, Ordenación Rápida que se usa todo el tiempo!

Ordenación rápida, rompe los grandes cubiertas en las pequeñas.Es decir, rompe las grandes tareas en pequeñas.

Hmmm.No puede ser una regla de ahí, creo.Para hacer grandes tareas pequeñas, separarlas.

Esta especie es muy rápido.Cómo de rápido?Big O, nos dice:este tipo de necesidades O(n log n) trabajo a realizar, en la media de caso.

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

La primera clase fue de O(n al cuadrado).Pero Ordenación Rápida es O(n log n).Usted sabe que n log n es menor que n al cuadrado, para la gran n, la derecha?Bien, que es como sabemos que el Quick Sort es rápido!

Si usted tiene que ordenar una baraja, ¿cuál es la mejor manera?Bueno, usted puede hacer lo que quiera, pero yo elegiría Ordenación Rápida.

¿Por qué debo elegir Ordenación Rápida?No me gusta trabajar, por supuesto!Quiero trabajar tan pronto como puedo lograr que se haga.

¿Cómo puedo saber Ordenación Rápida es menos trabajo?Sé que O(n log n) es menor que O(n al cuadrado).Los s son más pequeños, así Ordenación Rápida es menos trabajo!

Ahora usted sabe que mi amigo, el Gran O.Él nos ayuda a hacer menos trabajo.Y si usted sabe O grande, puede hacer menos trabajo también!

Has aprendido todo lo que conmigo!Eres tan inteligente!Muchas gracias!

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

[1]:Hay una forma de engañar y añadir todas las cosas de uno a n, todos a la vez.Algunas chico llamado Gauss se dio cuenta de esto cuando tenía ocho años.Yo no soy tan inteligente, aunque, por lo no me pregunten cómo lo hizo.

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

A continuación, O( <some expression X involving n> ) medios, en Inglés sencillo:

Si tiene la mala suerte al ejecutar A, puede ser que tome (n) operaciones a X completa.

Como suele suceder, hay ciertas funciones (pensar en ellos como implementaciones de X (n) ) que tienden a ocurrir con bastante frecuencia. Estos son bien conocidos y en comparación con facilidad (Ejemplos: 1, Log N, N, N^2, N!, etc ..)

Mediante la comparación de éstos cuando se habla de y otros algoritmos, es fácil de clasificar los algoritmos de acuerdo con el número de operaciones que pueden (peor caso) requerir a completar.

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

He modo más sencillo de comprender la complejidad del tiempo él métrica más común para el cálculo de complejidad del tiempo es la notación O grande. Esto elimina todos los factores constantes de manera que el tiempo de ejecución se puede estimar en relación a N como N tiende a infinito. En general se puede pensar en ello como esto:

statement;

es constante. El tiempo de ejecución de la instrucción no cambiará en relación con N

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

es lineal. El tiempo de ejecución del bucle es directamente proporcional a N. Cuando N 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ática. El tiempo de funcionamiento de los dos bucles es proporcional al cuadrado de N. Cuando N duplica, el tiempo de ejecución se incrementa 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ítmica. El tiempo de ejecución del algoritmo es proporcional a la cantidad de veces N puede ser dividido por 2. Esto es porque el algoritmo divide la zona de trabajo en un medio 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 se compone de los bucles de N (iterativo o recursivo) que son logarítmica, por lo tanto el algoritmo es una combinación de lineal y logarítmica.

En general, hacer algo con todos los elementos de una dimensión es lineal, hacer algo con todos los elementos de dos dimensiones es cuadrática, y dividiendo el área de trabajo a la mitad es logarítmica. Hay otras medidas Big O, como la raíz cúbica, exponenciales y cuadrado, pero no son tan comunes. notación Big O se describe como O () donde es la medida. El algoritmo quicksort se describiría como O (N * log (N)).

Nota: Nada de esto ha tenido en cuenta las mejores, promedio, y peores medidas del caso. Cada uno de ellos tendrá su propia notación O grande. 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 que he mostrado. También hay otras notaciones tales como ácidos grasos omega grande, pequeño o, y gran teta. Es probable que no se encontrará con ellos fuera de un curso de análisis de algoritmos.

Ver más en: aquí

Digamos que ordena Harry Potter: Completa 8-Film Collection [Blu-ray] de Amazon y descargar la misma colección de películas en línea al mismo tiempo. Que desea probar cuál es el método más rápido. La entrega tarda casi un día en llegar y la descarga se completó con unos 30 minutos antes. ¡Excelente! Así que es una apretada carrera.

¿Qué pasa si he pedido varias películas Blu-ray como El señor de los anillos, Crepúsculo, The Dark Knight Trilogy, etc., y descargar todas las películas en línea al mismo tiempo? Esta vez, la entrega todavía tomar un día para completar, pero la descarga en línea tarda 3 días para terminar. Para ir de compras en línea, el número de artículo comprado (entrada) no afecta al tiempo de entrega. La salida es constante. Llamamos a este O (1) .

Para la descarga en línea, el tiempo de descarga es directamente proporcional a los tamaños de los archivos de películas (de entrada). Llamamos a este O (n) .

A partir de los experimentos, se sabe que las compras en línea escala mejor que la descarga en línea. Es muy importante entender la notación O grande, ya que le ayuda a analizar la escalabilidad y eficiencia de algoritmos.

Nota: notación Big O representa la peor de los casos de un algoritmo. Vamos a suponer que O (1) y O (n) son los peores escenarios del ejemplo anterior.

referencia : http://carlcheo.com/compsci

Si usted tiene una adecuada noción de infinito en su cabeza, entonces no es una descripción muy breve:

Big O notación indica que el costo de la solución de un ser infinitamente grande problema.

Y además

Factores constantes son insignificantes

Si actualiza a una computadora que puede ejecutar el algoritmo dos veces más rápido, la notación big O no cuenta de que.Factor constante de mejoras son demasiado pequeños para que se noten en la escala que la notación big O trabaja.Tenga en cuenta que esto es parte intencional del diseño de big O notación.

Aunque algo "más grande" que un factor constante puede ser detectado, sin embargo.

Cuando los interesados en hacer cálculos cuyo tamaño es "grande" lo suficiente como para ser considerado como aproximadamente el infinito, entonces la notación big O es aproximadamente el costo de la solución de su problema.

Si el de arriba no tiene sentido, entonces usted no tiene un compatibles intuitiva de la noción de infinito en su cabeza, y probablemente debería caso omiso de todo lo anterior;la única forma que conozco para hacer estas ideas riguroso o explicar si no están ya intuitivamente útil, es para enseñar a los grandes de la O notación o algo similar.(aunque, una vez que se comprende muy bien la notación big O en el futuro, puede ser vale la pena volver a visitar estas ideas)

¿Qué es un inglés sencillo la explicación de la "Big O" notación?

Muy Rápida Nota:

La O en "Big O", se refiere a la "Orden"(o, precisamente, "orden")
así que usted podría conseguir su idea, literalmente, que se utiliza para pedir algo para comparar.

"Big O" hace dos cosas:
1. Calcula cuántos pasos del método que tu ordenador se aplica para realizar una tarea.
2. Facilitar el proceso de comparar con otros a fin de determinar si es bueno o no?
3. "Big O' alcanza los dos anteriores con estandarizado Notations.
Hay siete más utilizados notaciones
1. O(1), significa que su equipo obtiene una tarea hecha con 1 de paso, es excelente, Ordenó Nº 1
2. O(logN), significa que el equipo de completar una tarea con logN pasos, su buen estado, Ordenó Nº 2
3. O(N), terminar una tarea con N pasos, su feria, Nº de Orden 3
4. O(NlogN), termina una tarea con O(NlogN) pasos, no es bueno, Nº de Orden 4
5. O(N^2), consigue una tarea hecha con N^2 pasos, es malo, Nº de Orden 5
6. O(2^N), se obtiene una tarea hecha con 2^N pasos, es horrible, la Orden Nº 6
7. O(N!), consigue una tarea hecha con N! pasos, es terrible, la Orden Nº 7

Supongamos que usted consigue la notación O(N^2), no sólo tienes claro el método de toma de N*N pasos para realizar una tarea, también se puede ver que no es bueno que como O(NlogN) a partir de su clasificación.

Por favor, tenga en cuenta el orden en el extremo de la línea, sólo para su mejor comprensión.Hay más de 7 anotaciones si todas las posibilidades consideradas.

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

Además, Big O establece el peor de los casos, o medir la-límite Superior de los pasos.
Podría referirse a Big-Ω (Big-Omega) para el mejor de los casos.

Big-Ω (Big-Omega) notación (artículo) | Khan Academy

Resumen
"Big O", describe el algoritmo de rendimiento y la evalúa.

o en la dirección que formalmente, "Big O" clasifica los algoritmos y estandarizar el proceso de comparación.

La manera más sencilla de verlo (en la llanura Inglés)

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

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

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

Supongamos

n = número de parámetros de entrada

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

c = una constante

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

A continuación, tan lejos como Big O se refiere, la aproximación f (n) es considerada suficientemente buena, siempre y cuando la condición a continuación es cierto.

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

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

En la notación O grande Esto se escribe como

T(n)∈O(n)

Esto se lee como T de n es en gran O de n.

Volver a Inglés

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

O grande de n significa mi algoritmo se ejecuta al menos tan rápido como esto. No se puede mirar en la notación O grande de su algoritmo y decir que es lento. Sólo se puede decir que es rápida.

este a dar un tutorial de vídeo sobre Big O Universidad de California en Berkley. Es en realidad es un concepto simple. Si escucha el profesor Shewchuck (también conocido como Dios nivel maestro) explicarla, que va a decir "Oh, eso es todo lo que es!".

He encontrado una muy buena explicación acerca de la notación O grande especialmente para una persona que no es mucho en las matemáticas.

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

notación O grande se utiliza en informática para describir la actuación   o la complejidad de un algoritmo. Big O describe específicamente la   peor de los casos, y se puede utilizar para describir el tiempo de ejecución   requiere o se utiliza el espacio (por ejemplo, en la memoria o en el disco) por una   algoritmo.

Cualquiera que haya leído las perlas de programación o cualquier otra Ciencias de la Computación   libros y no tiene una conexión a tierra en Matemáticas se han topado con un muro   cuando alcanzaron capítulos que mencionan O (N log N) o de otro aparentemente   sintaxis loco. Esperemos que este artículo le ayudará a obtener una   comprensión de los conceptos básicos de Big O y logaritmos.

Como programador primera y una segunda matemático (o tal vez tercera o   cuarto) He encontrado la mejor manera de entender Big O era a fondo para   producir algunos ejemplos en código. Por lo tanto, a continuación son algunas órdenes comunes de   crecimiento junto con descripciones y ejemplos en los que sea posible.

O (1)

O (1) describe un algoritmo que siempre va a 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; } O(N)
O (N)

O (N) describe un algoritmo cuyo rendimiento crecerán linealmente y   en proporción directa con el tamaño del conjunto de datos de entrada. El ejemplo   a continuación también demuestra cómo Big O favorece el rendimiento del peor caso   guión; una cadena coincidente se pudo encontrar durante cualquier iteración de la   de bucle y la función volvería pronto, pero la notación O grande se   siempre ha de asumir el límite superior, donde el algoritmo llevará a cabo la   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 implican anidadas iteraciones sobre los datos   conjunto. iteraciones más profundo anidados resultarán en 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 dobla con cada additon a   el conjunto de datos de entrada. La curva de crecimiento de un O función (2 ^N) es   exponencial - partiendo muy poco profunda, seguida de un aumento meteórica. Un   ejemplo de una función O (2 ^N) es el cálculo recursivo de Fibonacci   números:
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ícil de explicar lo que voy a utilizar un común   ejemplo:

La búsqueda binaria es una técnica utilizada para buscar los conjuntos de datos ordenados. Funciona   seleccionando el elemento medio del conjunto de datos, esencialmente el   la mediana, y la compara con un valor objetivo. Si los valores coinciden con lo   volverá éxito. Si el valor objetivo es mayor que el valor de   el elemento de sonda que tomará la mitad superior del conjunto de datos y   realizar la misma operación en contra de ella. Asimismo, si el valor objetivo   es menor que el valor del elemento de sonda se llevará a cabo la   operación contra la mitad inferior. Continuará reducir a la mitad los datos   establecer con cada iteración hasta que se ha encontrado el valor o hasta que pueda   Ya no dividir el conjunto de datos.

Este tipo de algoritmo se describe como O (log N). La reducción a la mitad iterativo   de los conjuntos de datos que se describen en el ejemplo de búsqueda binaria produce un crecimiento   curva que alcanza su máximo al principio y poco a poco se aplana como el tamaño   de los conjuntos de datos aumentan, por ejemplo, un conjunto de datos de entrada que contiene 10 artículos   toma un segundo para completar, un conjunto de datos que contiene 100 elementos toma   dos segundos, y un conjunto de datos que contiene 1000 elementos se llevará a tres   segundos. Duplicando el tamaño del conjunto de datos de entrada tiene poco efecto sobre lasu crecimiento como después de una única iteración del algoritmo del conjunto de datos   será reducido a la mitad y, por tanto, a la par de un conjunto de datos de entrada establecidos mitad de la   Talla. Esto hace que los algoritmos de búsqueda binaria como extremadamente eficiente   cuando se trata de grandes conjuntos de datos.

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

Digamos que su algoritmo de tratar el problema depende de algunos factores '', por ejemplo, vamos a hacer que N y X.

En función de N y X, el algoritmo requerirá algunas operaciones, por ejemplo, en el caso peor es 3(N^2) + log(X) operaciones.

Desde Big-O no se preocupa demasiado por el factor constante (aka 3), el Big-S de su algoritmo es O(N^2 + log(X)). Básicamente se traduce 'el importe de las operaciones de su algoritmo necesita para el peor de los casos se escala con este'.

Prefacio

algoritmo : procedimiento / fórmula para la solución de un problema

¿Cómo analizar algoritmos y cómo podemos comparar los algoritmos uno contra el otro?

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

notación Big-O:. describe lo rápido tiempo de ejecución crecerá en relación con la entrada como la entrada de llegar arbitrariamente grande

3 puntos clave:

Compare lo rápido que crece el tiempo de ejecución no comparar los tiempos de ejecución exactos (depende del hardware)
sólo se refiere a tiempo de ejecución crecen en relación con la entrada (n)
Como n obtiene arbitrariamente grande, se centran en los términos que van a crecer más rápido a medida que n se hace grande (piensa infinito) También conocido como análisis asintótico

complejidad espacial: aparte de la complejidad del tiempo, también nos preocupamos por la complejidad del espacio (la cantidad de memoria / espacio utiliza un algoritmo). En lugar de comprobar el tiempo de las operaciones, comprobamos el tamaño de la asignación de memoria.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow

¿Qué es un inglés sencillo la explicación de la "Big O" notación?

El Libro De Teléfono

El Viajante De Comercio

Polinomio Tiempo

O (1)

O (N)

O (N 2 )

O (2 N )

logaritmos

Prefacio

O (N ²)

O (2 ^N)