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


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


4529
2018-01-28 11:10


origen


Respuestas:


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


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

Big O Analysis

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

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

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

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

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

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

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

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

La adición es la más simple. Usted alinea los números hacia arriba (a la derecha) y agrega los dígitos en una columna escribiendo el último número de esa suma en el resultado. La parte de "decenas" de ese número se transfiere a la siguiente columna.

Supongamos que la adición de estos números es la operación más costosa en este algoritmo. Es lógico que para sumar estos dos números tengamos que sumar 6 dígitos (y posiblemente tener un 7mo). Si sumamos dos números de 100 dígitos, tendremos que hacer 100 adiciones. Si agregamos dos Números de 10,000 dígitos tenemos que hacer 10,000 adiciones.

Ver el patrón? los complejidad (siendo el número de operaciones) es directamente proporcional a la cantidad de dígitos norte en el número más grande. Nosotros llamamos esto En) o complejidad lineal.

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

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

Si tenemos dos números de 100 dígitos, tenemos que hacer 10,000 multiplicaciones y 200 adiciones. Para dos números de un millón de dígitos, necesitamos hacer un billón (1012) multiplicaciones y dos millones de adiciones.

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

Solo nos preocupamos por la parte más importante de la complejidad.

El astuto puede haberse dado cuenta de que podríamos expresar el número de operaciones como: n2 + 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 vuelve insignificante (representando el 0,0002% del total de las operaciones en esa etapa).

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

El listín telefónico

El siguiente mejor ejemplo en el que puedo pensar es en la guía telefónica, normalmente llamada White Pages o similar, pero puede variar de un país a otro. Pero estoy hablando de uno que enumera personas por apellido y luego iniciales o nombre, posiblemente dirección y luego números de teléfono.

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

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

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

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

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

Eso es asombrosamente bueno, ¿no?

En términos de Big-O, esto es O (log n) o complejidad logarítmica. Ahora el logaritmo en cuestión podría ser ln (base e), log10, Iniciar sesión2 o alguna otra base. No importa que siga siendo O (log n) igual que O (2n2) y O (100n2) siguen siendo ambos O (n2)

Vale la pena en este punto explicar que Big O se puede usar para determinar tres casos con un algoritmo:

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

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

Volver a la guía telefónica.

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

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

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

  • Mejor caso: O (1);
  • Caso esperado: O (n) (para 500,000); y
  • Peor de los casos: O (n) (para 1,000,000).

El vendedor ambulante

Este es un problema bastante famoso en informática y merece una mención. En este problema tienes N pueblos. Cada uno de esos pueblos está vinculado a 1 o más ciudades por un camino de cierta distancia. El problema del Viajero Vendedor es encontrar el recorrido más corto que visita cada ciudad.

Suena simple? Piensa otra vez.

Si tienes 3 ciudades A, B y C con caminos entre todos los pares, entonces puedes ir:

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

Bueno, en realidad hay menos que eso porque algunos de estos son equivalentes (A → B → C y C → B → A son equivalentes, por ejemplo, porque utilizan las mismas carreteras, solo al revés).

En realidad hay 3 posibilidades.

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

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

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

Entonces, el problema de Big-O of the Traveling Sellerman es ¡En!) o complejidad factorial o combinatoria.

Cuando llegas a 200 ciudades ya no queda suficiente tiempo en el universo para resolver el problema con las computadoras tradicionales.

Algo sobre lo que pensar.

Tiempo polinomial

Otro punto que quería mencionar rápidamente es que cualquier algoritmo que tiene una complejidad de Enun) se dice que tiene complejidad polinomial o es solucionable en tiempo polinomial.

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

De todos modos, eso es todo por mi explicación (afortunadamente sencilla) de Big O (revisada).


6089
2018-01-28 11:18



Muestra cómo se escala un algoritmo.

En2): conocido como Complejidad cuadrática

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

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

En): conocido como Complejidad lineal

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

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

O (1): conocido como Complejidad constante

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

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

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

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

La cantidad de cálculos solo se incrementa mediante un registro del valor de entrada. Entonces, en este caso, suponiendo que cada cómputo demora 1 segundo, el registro de la entrada n es el tiempo requerido, de ahí log n.

Esa es la esencia de eso. Reducen las matemáticas por lo que podría no ser exactamente n2 o lo que digan que es, pero ese será el factor dominante en la escalada.


662
2018-01-28 11:28



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


Lo esencial

para entradas "suficientemente grandes" ...

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

la notación big-O no se preocupa por factores constantes: la función 9x² se dice que "crece exactamente como" 10x². Tampoco lo hace la gran O asintótico notación cuidado sobre no asintótico cosas ("cosas cerca del origen" o "lo que sucede cuando el tamaño del problema es pequeño"): la función 10x² se dice que "crece exactamente como" 10x² - x + 2.

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

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

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

... esto significa que para tamaños de problema "suficientemente grandes" N (si ignoramos las cosas cerca del origen), existe alguna constante (por ejemplo, 2.5, completamente inventada) tal que:

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

Hay muchas opciones de constante; a menudo la "mejor" elección se conoce como el "factor constante" del algoritmo ... pero a menudo lo ignoramos al ignorar los términos no más grandes (ver la sección Factores constantes para saber por qué generalmente no importan). También puede pensar en la ecuación anterior como un límite, diciendo "En el peor de los casos, el tiempo que tome nunca será peor que aproximadamente N*log(N), dentro de un factor de 2.5 (un factor constante que no nos importa mucho)".

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


Aplicaciones

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

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

Ejemplo

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

Copia de seguridad un poco: la cantidad de handshakes es exactamente n-choose-2 o N*(N-1)/2 (Cada una de N personas estrecha la mano de N-1 a otras personas, pero esto cuenta dos veces los apretones de manos para dividir por 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Sin embargo, para un gran número de personas, el término lineal N está empequeñecido y efectivamente contribuye 0 a la razón (en el gráfico: la fracción de casillas vacías en la diagonal sobre el total de casillas se reduce a medida que aumenta el número de participantes). Por lo tanto, el comportamiento de escalado es order N², o la cantidad de apretones de manos "crece como N²".

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

Es como si los cuadros vacíos en la diagonal del gráfico (N * (N-1) / 2 marcas de verificación) ni siquiera estuvieran allí (N2 marcas de verificación asintóticamente).

(Divagación temporal del "inglés simple" :) Si quisieras probar esto para ti mismo, podrías realizar un álgebra simple sobre la razón para dividirla en múltiples términos (limsignifica "considerado en el límite de", simplemente ignórelo si no lo ha visto, es solo una notación para "y N es realmente muy grande"):

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

tl; dr: El número de apretones de manos parece "x² tanto para valores grandes, que si tuviéramos que escribir la relación # handshakes / x², el hecho de que no necesitamos exactamente x² handshakes ni siquiera aparecerían en el decimal durante un tiempo arbitrariamente grande.

p.ej. para x = 1million, ratio # handshakes / x²: 0.499999 ...


Construyendo la intuición

Esto nos permite hacer declaraciones como ...

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


362
2017-07-08 04:46



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

En una frase: a medida que aumenta el tamaño de tu trabajo, ¿cuánto tiempo más lleva completarlo?

Obviamente, eso solo está utilizando el "tamaño" como la entrada y el "tiempo tomado" como salida. Se aplica la misma idea si quiere hablar sobre el uso de la memoria, etc.

Aquí hay un ejemplo donde tenemos N camisetas que queremos secar. Bien asumir es increíblemente rápido colocarlos 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 ...

  • Usar una línea de lavado afuera: suponiendo que tiene un patio trasero infinitamente grande, el lavado se seca en O (1) vez. Por mucho que lo tenga, obtendrá el mismo sol y aire fresco, por lo que el tamaño no afectará el tiempo de secado.

  • Usando una secadora: pones 10 camisas en cada carga, y luego se hacen una hora más tarde. (Ignore los números reales aquí - son irrelevantes.) Así que secar 50 camisas acerca de 5 veces más largo que secar 10 camisas.

  • Poniendo todo en un armario ventilado: si ponemos todo en una gran pila y dejamos que la calidez general lo haga, las camisas medias tardarán mucho en secarse. No me gustaría adivinar los detalles, pero sospecho que esto es al menos O (N ^ 2) - a medida que aumenta la carga de lavado, el tiempo de secado aumenta más rápido.

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

¿Esto hace que una tabla hash sea más rápida que una matriz para búsquedas? No necesariamente. Si tiene una colección muy pequeña de entradas, una matriz puede ser más rápida: puede verificar todas las cadenas en el tiempo necesario para calcular el código hash de la que está mirando. A medida que el conjunto de datos crece, sin embargo, la tabla hash vencerá a la matriz.


237
2018-01-28 11:16



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

Ejemplos:

  • O (n): si duplico el tamaño de entrada, el tiempo de ejecución se duplica

  • En2): Si el tamaño de entrada duplica el tiempo de ejecución se cuadruplica

  • O (log n): si el tamaño de entrada se duplica el tiempo de ejecución aumenta en uno

  • O (2norte): Si el tamaño de entrada aumenta en uno, el tiempo de ejecución se duplica

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


120
2018-01-28 11:23



La notación Big O es comúnmente utilizada por los programadores como una medida aproximada del tiempo que un cálculo (algoritmo) llevará a completar expresado como una función del tamaño del conjunto de entrada.

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

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

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

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

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


97
2017-09-05 16:31



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

A menudo puede ver O (n), O (n2), O (nlogn) y demás, todas estas son solo formas de mostrar; ¿Cómo cambia un algoritmo?

O (n) significa Big O is n, y ahora usted podría pensar: "¿Qué es n?" Bueno, "n" es la cantidad de elementos. Imagine que desea buscar un elemento en una matriz. Tendría que buscar en Cada elemento y como "¿Es usted el elemento / elemento correcto?" en el peor de los casos, el ítem está en el último índice, lo que significa que se tomó tanto tiempo como elementos en la lista, así que para ser genéricos, decimos "¡oye, n es una cantidad justa de valores!" .

Así que entonces puedes entender lo que "n2"significa, pero para ser aún más específico, juega con la idea de que tienes un simple, el más simple de los algoritmos de clasificación: bubblesort. Este algoritmo necesita examinar toda la lista, para cada elemento.

Mi lista

  1. 1
  2. 6
  3. 3

El flujo aquí sería:

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

Esto es O n2 porque, necesita mirar todos los artículos en la lista, hay "n" elementos. Para cada elemento, mira todos los elementos una vez más, para comparar, esto también es "n", por lo que para cada elemento, se ve "n" veces que significa n * n = n2

Espero que esto sea tan simple como lo desees.

Pero recuerda, Big O es solo una forma de extenderte a ti mismo en la forma de tiempo y espacio.


77
2018-01-28 11:14



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

Hay una gran cantidad de información que Big O no le informa sobre un algoritmo dado. Corta al hueso y solo brinda información sobre la naturaleza de escalado de un algoritmo, específicamente cómo el uso de recursos (tiempo de reflexión o memoria) de un algoritmo se amplía en respuesta al "tamaño de entrada".

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

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

Considere el ejemplo de clasificación canónica. Bubble-sort es O (n2) mientras que merge-sort es O (n log n). Supongamos que tiene dos aplicaciones de clasificación, la aplicación A que utiliza sorti de burbuja y la aplicación B que usa clasificación de fusión, y digamos que para tamaños de entrada de alrededor de 30 elementos, la aplicación A es 1.000 veces más rápida que la aplicación B al ordenar. Si nunca tiene que ordenar mucho más de 30 elementos, entonces es obvio que debería preferir la aplicación A, ya que es mucho más rápida en estos tamaños de entrada. Sin embargo, si encuentra que debe ordenar diez millones de artículos, entonces lo que esperaría es que la aplicación B en realidad termine siendo miles de veces más rápida que la aplicación A en este caso, completamente debido a la forma en que cada algoritmo escala.


52
2018-01-28 13:12



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

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

O (1):

Sin crecimiento. Independientemente de cuán grande sea el problema, puede resolverlo en la misma cantidad de tiempo. Esto es algo análogo a la radiodifusión, donde se requiere la misma cantidad de energía para transmitir a una distancia determinada, independientemente de la cantidad de personas que se encuentren dentro del rango de transmisión.

O (registro norte)

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

O (norte)

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

O (norte Iniciar sesión norte)

Esta complejidad es muy similar a O (norte). Para todos los propósitos prácticos, los dos son equivalentes. Este nivel de complejidad generalmente se consideraría escalable. Al ajustar las suposiciones, O (norte Iniciar sesión norte) los algoritmos se pueden transformar en O (norte) algoritmos. Por ejemplo, limitar el tamaño de las teclas reduce la clasificación de O (norte Iniciar sesión norte) a O (norte).

O (norte2)

Crece como un cuadrado, donde norte es la longitud del lado de un cuadrado. Esta es la misma tasa de crecimiento que el "efecto de red", donde todos en una red pueden conocer a todos los demás en la red. El crecimiento es costoso La mayoría de las soluciones escalables no pueden usar algoritmos con este nivel de complejidad sin hacer gimnasia significativa. Esto generalmente se aplica a todas las demás complejidades polinómicas: O (nortek) - también.

O (2norte)

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


35
2018-01-27 23:09



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

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

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

y así.


34
2018-01-28 11:19



Es muy difícil medir la velocidad de los programas de software, y cuando lo intentamos, las respuestas pueden ser muy complejas y llenas de excepciones y casos especiales. Este es un gran problema, porque todas esas excepciones y casos especiales son molestos e inútiles cuando queremos comparar dos programas diferentes entre nosotros para saber cuál es el "más rápido".

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

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

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

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

El bueno:

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

El malo:

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

... y lo feo

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

30
2018-05-29 13:51