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

pregunta creada en Fri, Jul 22, 2016 12:00 AM

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

    
4766
  1. Resumen: El límite superior de la complejidad de un algoritmo. Vea también la pregunta similar Big O, ¿cómo la calcula /aproxima? para una buena explicación.
    2009-01-28 11: 18: 44Z
  2. Las otras respuestas son bastante buenas, solo un detalle para entenderlo: O (log n) o similar, que depende de la "longitud" o el "tamaño" de la entrada, no en el valor en sí. Esto podría ser difícil de entender, pero es muy importante. Por ejemplo, esto sucede cuando su algoritmo divide las cosas en dos en cada iteración.
    2009-01-28 11: 23: 43Z
  3. Hay una conferencia dedicada a la complejidad de los algoritmos en la Lectura 8 del curso "Introducción a la Informática y Programación" del MIT youtube.com/watch?v=ewd7Lf2dr5Q No es completamente inglés, pero brinda una explicación agradable con ejemplos que son fácilmente comprensibles.
    2010-07-17 20: 57: 40Z
  4. Big O es una estimación del peor desempeño de una función que asume que el algoritmo realizará el número máximo de iteraciones.
    2012-08-28 00: 16: 57Z
  5. 2013-09-07 18: 02: 25Z
30 Respuestas                              30                         

Nota rápida, esto es casi seguro que confunde Notación Big O (que es un límite superior) con notación Theta (que es un enlace 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 elegidas deliberadamente en esa oración:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

La guía telefónica

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

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

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

Esto se denomina 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 una guía telefónica de un millón de nombres, puede encontrar cualquier nombre haciendo esto como máximo 20 veces. Al comparar los algoritmos de búsqueda, decidimos que esta comparación es nuestra 'n'.

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

Eso es asombrosamente bueno, ¿no?

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

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

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

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

Volver a la guía telefónica.

¿Qué sucede si tiene un número de teléfono y desea buscar 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?

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

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

  
  • Mejor caso: O (1);
  •   
  • Caso esperado: O (n) (para 500,000); y
  •   
  • El peor caso: O (n) (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 una de esas ciudades está vinculada a una o más ciudades por una carretera de cierta distancia. El problema del vendedor ambulante es encontrar el recorrido más corto que visita cada ciudad.

¿Suena simple? Piensa de nuevo.

Si tienes 3 ciudades A, B y C con carreteras entre todos los pares, 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 ellos son equivalentes (A → B → C y C → B → A son equivalentes, por ejemplo, porque usan las mismas carreteras, justo al revés).

En la actualidad hay 3 posibilidades.

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

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

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

Por lo tanto, la gran O del problema del vendedor ambulante es O (n!) o complejidad factorial o combinatoria .

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

Algo en que pensar.

Tiempo polinomial

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

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

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

    
6390
2017-06-30 03: 17: 23Z
  1. Mientras que las otras respuestas se enfocan en explicar las diferencias entre O (1), O (n ^ 2) et al ... suya es la que detalla cómo los algoritmos se puede clasificar en n ^ 2, nlog (n) etc. +1 para obtener una buena respuesta que me ayudó a entender la notación Big O también
    2009-01-28 11: 42: 39Z
  2. es posible que desee agregar que big-O representa un límite superior (dado por un algoritmo), big-Omega otorga un límite inferior (generalmente dado como una prueba independiente de un algoritmo específico) y Big-Theta significa que se conoce un algoritmo "óptimo" que alcanza ese límite inferior.
    2009-02-02 19: 16: 22Z
  3. Esto es bueno si está buscando la respuesta más larga, pero no la respuesta que mejor exp.lains Big-O de una manera simple.
    2010-07-16 18: 21: 59Z
  4. - 1: Esto es evidentemente incorrecto: _ "BigOh es una representación relativa de la complejidad del algoritmo". No. BigOh es un límite superior asintótico y existe bastante bien independiente de la informática. O (n) es lineal. No, estás confundiendo a BigOh con theta. log n es O (n). 1 es O (n). El número de upvotes a esta respuesta (y los comentarios), que comete el error básico de confundir a Theta con BigOh es bastante vergonzoso ...
    2011-05-24 04: 44: 04Z
  5. "Cuando llegas a 200 ciudades, no queda suficiente tiempo en el universo para resolver el problema con las computadoras tradicionales". Cuando el universo va a terminar?
    2012-06-18 10: 43: 39Z

Muestra cómo se escala un algoritmo.

O (n 2 ) : conocido como Complejidad cuadrática

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

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

O (n) : conocido como Complejidad lineal

  • 1 elemento: 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, por lo tanto, el factor de escala de O (n) es 10.

O (1) : conocido como Constante complejidad

  • 1 elemento: 1 segundo
  • 10 artículos: 1 segundo
  • 100 artículos: 1 segundo

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

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

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

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

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

    
696
2014-10-13 16: 53: 20Z
  1. ¿Qué significa exactamente esta definición? (El número de elementos sigue aumentando en un factor de 10, pero el factor de escala de O (1) siempre es 1.)
    2010-03-25 22: 10: 14Z
  2. No segundos, operaciones. Además, te perdiste el tiempo factorial y logarítmico.
    2010-07-17 01: 27: 04Z
  3. Esto no explica muy bien que O (n ^ 2) podría estar describiendo un algoritmo que se ejecute precisamente en .01 * n ^ 2 + 999999 * n + 999999 . Es importante saber que los algoritmos se comparan utilizando esta escala y que la comparación funciona cuando n es 'suficientemente grande'. El orden del tiempo de Python en realidad utiliza la ordenación por inserción (caso peor /promedio O (n ^ 2)) para arreglos pequeños debido al hecho de que tiene una pequeña sobrecarga.
    2012-05-21 23: 14: 36Z
  4. Esta respuesta también confunde la notación O grande y la notación Theta. La función de n que devuelve 1 para todas sus entradas (normalmente, simplemente se escribe como 1) está en realidad en O (n ^ 2) (aunque también está en O (1)). De manera similar, un algoritmo que solo tiene que hacer un paso que toma una cantidad constante de tiempo también se considera un algoritmo O (1), pero también un algoritmo O (n) y un algoritmo O (n ^ 2). Pero tal vez los matemáticos y los informáticos no estén de acuerdo con la definición: - /.
    2013-08-08 11: 11: 24Z
  5. La complejidad logarítmica O (log n) considerada en esta respuesta es de la base 10. Generalmente, el estándar es calcular con la base 2. Se debe tener en cuenta este hecho y no debe confundirse. También como lo menciona @ChrisCharabaruk, la complejidad denota el número de operaciones y no segundos.
    2016-02-17 06: 46: 36Z

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


Básico

para "suficientemente" entradas grandes ...

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

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

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

Dicho de otra manera, se trata de la relación a medida que avanza hasta el infinito. Si divide el tiempo real que toma el O(...), obtendrá un factor constante en el límite de entradas grandes. Intuitivamente esto tiene sentido: las funciones se "escalan" entre sí si puede multiplicar una para conseguir el otro 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 grandes" tamaños de problema N (si ignoramos cosas cerca del origen), existe una constante (por ejemplo, 2.5, completamente inventado) tal que:

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

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

En general, O(...) es el más útil porque a menudo nos preocupamos por el peor comportamiento. Si f(x) representa algo "malo" como el uso del procesador o la memoria, entonces "f(x) ∈ O(upperbound)" significa que "upperbound es el peor escenario de uso del 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 discutir las asintóticas de cualquier cosa en la que la escala sea significativa, como:

  • el número de posibles apretones de manos entre N personas en una fiesta (Ɵ(N²), específicamente N(N-1)/2, pero lo que importa es que "escala como" )
  • cantidad probabilística esperada de personas que han visto algún marketing viral en función del tiempo
  • cómo se escala la latencia del sitio web con la cantidad de unidades de procesamiento en una CPU o GPU o en un grupo de computadoras
  • cómo las salidas de calor en la CPU mueren en función del conteo de transistores, voltaje, etc.
  • cuánto tiempo debe ejecutarse 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 anterior del apretón de manos, todos en una habitación dan la mano a todos los demás. En ese ejemplo, #handshakes ∈ Ɵ(N²). ¿Por qué?

Retrocede un poco: la cantidad de apretones de manos es exactamente n-elige-2 o N*(N-1)/2 (cada una de N personas sacude las manos de otras personas de N-1, pero este doble conteo de apretones de manos se divide por 2):

todos apretones de manos a todos los demás. Crédito de imagen y licencia por wikipedia /wikimedia commons "gráfico completo" artículo. matriz de adyacencia

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

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

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

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

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

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

  

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


Intuición de construcción

Esto nos permite hacer declaraciones como ...

  

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

  • ... doble el tiempo que toma un algoritmo O (N) ("tiempo lineal") ".
      

    N → (2N) = 2 ( N )

  • ... Yo cuadruplicé (cuadruplicé) el tiempo que tarda un algoritmo O (N²) ("tiempo cuadrático"). " (por ejemplo, un problema 100x tan grande toma 100² = 10000x el tiempo ... posiblemente insostenible)
      

    → (2N) ² = 4 ()

  • ... Doble cubos (octuple) el tiempo que toma un algoritmo O (N³) ("tiempo cúbico"). " (por ejemplo, un problema 100x tan grande toma 100³ = 1000000x todo el tiempo ... muy insostenible)
      

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

  • ... agrego una cantidad fija al tiempo que toma un algoritmo O (log (N)) ("tiempo logarítmico"). " (¡barato!)
      

    c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (cantidad fija) + ( registro c (N) )

  • ... No cambio el tiempo que toma un algoritmo O (1) ("tiempo constante"). " (¡el más barato!)
      

    c * 1 c*1

  • ... I "(básicamente) duplica" el tiempo que tarda un algoritmo O (N log (N)). " (bastante común)
      

    es menor que O (N 1.000001 ), lo que podrías estar dispuesto a llamar básicamente lineal

  • ... Incremento ridículamente el tiempo que toma el algoritmo O (2 N ) ("tiempo exponencial"). " (doblarías (o triplicarías, etc.) el solo por aumentar el problema en una sola unidad)
      

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

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

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

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

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


Factores constantes

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

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


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

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

Lo mismo se puede decir para el mismo acto de escribir . Todos los algoritmos que imprimen N cosas tomarán N tiempo, porque la salida es al menos tan larga (por ejemplo, la impresión de todas las permutaciones (formas de reorganizar) un conjunto de N naipes es factorial: O(N!)).

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

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

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

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


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

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

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

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

 
for(i=0; i<A; i++)        // A * ...
    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, es posible que aún puedas imaginar lo que está sucediendo:

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

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

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

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

Aquí hay otra cosa que podemos reconocer visualmente:

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

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

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

O tal vez logre (N) pasar los datos, por O (N * log (N)) tiempo total:

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

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

 
[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Si hacemos algo muy complicado, como con una función recursiva o un algoritmo de divide y vencerás, puedes usar Teorema maestro (generalmente funciona), o en casos ridículos, el teorema de Akra-Bazzi (casi siempre funciona) busca el tiempo de ejecución de su algoritmo en Wikipedia.

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


Complejidad amortizada y media de casos

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

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

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

  

La analogía para el análisis amortizado:

     

Conduce un coche. Ocasionalmente, necesitas pasar 10 minutos yendo a   La gasolinera y luego pasar 1 minuto rellenando el tanque con gasolina.   Si hiciste esto cada vez que fuiste con tu auto (pasa 10   minutos conduciendo a la gasolinera, pasar unos segundos llenando un   fracción de un galón), sería muy ineficiente. Pero si te llenas   tup el tanque una vez cada pocos días, los 11 minutos pasados ​​conduciendo a la   la estación de servicio se "amortiza" en un número suficientemente grande de viajes,   que puede ignorarlo y pretender que todos sus viajes fueron un 5% más largos.

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

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

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

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

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


Big-O multidimensional

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


Toda la historia

Tenga en cuenta que la gran O no es toda la historia. Puede acelerar drásticamente algunos algoritmos utilizando el almacenamiento en caché, haciéndolos inconscientes de la memoria caché, evitando cuellos de botella trabajando con RAM en lugar de disco, usando paralelización o haciendo trabajos antes de tiempo. Estas técnicas a menudo son independientes de la notación "O grande" de orden de crecimiento, aunque a menudo verá la cantidad de núcleos en la notación O grande de algoritmos paralelos.

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

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

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

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

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


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

Addenda matemática

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

La gente a menudo usará const1*g(x), que es quizás la notación más correcta de 'comp-sci', y completamente legítima de usar; "f = O (...)" se lee "f es orden ... /f está limitado por xxx por ..." y se considera que "f es una expresión cuyos asintóticos son ...". Me enseñaron a usar el const2*g(x) más riguroso. == significa "es un elemento de" (aún leído como antes). = O(...) es en realidad una clase de equivalencia , es decir, es un conjunto de cosas que consideramos iguales. En este caso particular, ∈ O(...) contiene elementos como {, O(N²), O(N²), 2 N², 3 N², ...} y es infinitamente grande, pero sigue siendo un conjunto. La notación 1/2 N² podría ser la más común, e incluso se usa en documentos de científicos informáticos de renombre mundial. Además, a menudo ocurre que en un ambiente informal, la gente dirá 2 N² + log(N) cuando signifique - N² + N^1.9; Esto es técnicamente cierto ya que el conjunto de cosas = es un subconjunto de O(...) ... y es más fácil de escribir. ;-)

    
381
2018-11-14 08: 13: 05Z
  1. Una excelente respuesta matemática, pero el OP solicitó una respuesta simple en inglés. Este nivel de descripción matemática no es necesario para comprender la respuesta, aunque para las personas que tienen una mentalidad matemática en particular, puede ser mucho más fácil de entender que el "lenguaje simple". Sin embargo, el OP pidió este último.
    2013-07-02 22: 19: 52Z
  2. Presumiblemente, las personas que no sean el OP podrían tener interés en las respuestas a esta pregunta. ¿No es ese el principio rector del sitio?
    2014-02-03 18: 34: 33Z
  3. Aunque quizás pueda ver por qué la gente puede hojear mi respuesta y pensar que es demasiado matemática (especialmente el "matemático es el nuevo inglés simple", ya que se eliminaron), La pregunta original se refiere a la gran O, que es acerca de las funciones, así que intento ser explícito y hablar sobre las funciones de una manera que complemente la intuición en inglés simple. Las matemáticas aquí a menudo se pueden pasar por alto, o entenderse con un fondo de matemáticas de escuela secundaria. Sin embargo, creo que la gente puede ver las Addenda de Matemáticas al final, y supongo que es parte de la respuesta, cuando está simplemente ahí para ver cómo se ve la matemática real .
    2015-04-03 04: 39: 54Z
  4. Esta es una respuesta fantástica; OMI mucho mejor que tEl que tiene más votos. La "matemática" requerida no va más allá de lo que se necesita para comprender las expresiones entre paréntesis después de la "O", que no puede evitarse una explicación razonable que use ejemplos.
    2016-04-27 15: 52: 07Z
  5. "f (x) ∈ O (límite superior) significa que f" no crece más rápido que "límite superior" estos tres simplemente redactados, pero matemáticamente son correctas las explicaciones de los grandes Oh, Theta, y los omega son dorados. Me describió en un lenguaje sencillo el punto que 5 fuentes diferentes no podían traducirme sin escribir expresiones matemáticas complejas. ¡Gracias hombre! :)
    2016-09-04 22: 20: 10Z

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

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

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

Este es un ejemplo en el que tenemos N camisetas que queremos secar. Supondremos que 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 ...

  • Usando una línea de lavado en el exterior: asumiendo que tiene un patio trasero infinitamente grande, el lavado se seca en O (1). Por mucho que tengas, obtendrá el mismo sol y aire fresco, por lo que el tamaño no afecta el tiempo de secado.

  • Usando una secadora: colocas 10 camisas en cada carga, y luego se terminan una hora más tarde. (Ignore los números reales aquí, son irrelevantes). Por lo tanto, secar 50 camisas toma aproximadamente 5 veces más que secar 10 camisetas.

  • Poner todo en un armario de ventilación: si ponemos todo en una pila grande y dejamos que el calor general lo haga, la camisa del medio tardará mucho tiempo en secarse. No me gustaría adivinar los detalles, pero sospecho que esto es al menos O (N ^ 2): a medida que aumenta la carga de lavado, el tiempo de secado aumenta más rápidamente.

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

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

    
241
2011-11-08 06: 15: 21Z
  1. Una tabla hash requiere que se ejecute un algoritmo para calcular el índice de la matriz real (según la implementación). Y una matriz solo tiene O (1) porque es solo una dirección. Pero esto no tiene nada que ver con la pregunta, solo una observación :)
    2009-01-28 11: 29: 54Z
  2. la explicación de Jon tiene mucho que ver con la pregunta que creo. es exactamente cómo se lo podría explicar a una madre, y ella finalmente lo entendería, creo :) Me gusta el ejemplo de la ropa (en particular, la última, donde explica el crecimiento exponencial de la complejidad)
    2009-01-28 11: 32: 26Z
  3. Filip: No estoy hablando de direccionar una matriz por índice, estoy hablando de encontrar una entrada coincidente en una matriz. ¿Podría volver a leer la respuesta y ver si eso aún no está claro?
    2009-01-28 11: 35: 58Z
  4. @ Filip Ekberg Creo que estás pensando en una tabla de direcciones directas donde cada índice se asigna a una clave directamente, por lo tanto, es O (1), sin embargo, creo que Jon es hablando de una matriz no clasificada de pares clave /valor que debe buscar linealmente.
    2011-07-29 09: 41: 13Z
  5. @ RBT: No, no es una búsqueda binaria. Puede llegar al hash correcto bucket inmediatamente, solo en función de una transformación de código hash a índice de bucket. Después de eso, encontrar el código hash correcto en el cubo puede ser lineal o puede ser una búsqueda binaria ... pero para ese momento ya se ha reducido a una proporción muy pequeña del tamaño total del diccionario.
    2016-11-17 07: 57: 40Z

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 aumentan de tamaño.

Ejemplos:

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

  • O (n 2 ): si el tamaño de entrada duplica las cuadruplicaciones del tiempo de ejecución

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

  • O (2 n ): si el tamaño de la 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.

    
123
2014-01-11 11: 11: 19Z
  1. incorrecto! por ejemplo, O (n): si doblo el tamaño de entrada, el tiempo de ejecución se multiplicará a una constante finita no cero. Me refiero a O (n) = O (n + n)
    2010-05-16 11: 33: 33Z
  2. Estoy hablando de la f en f (n) = O (g (n)), no la g como parece que entiendes.
    2010-08-06 12: 30: 15Z
  3. Upvote, pero la última oración no aporta mucho lo que siento. No hablamos a menudo de "bits" cuando discutimos o medimos Big (O).
    2011-09-05 16: 41: 08Z
  4. Debes agregar un ejemplo para O (n log n).
    2011-09-22 15: 50: 33Z
  5. Eso no es tan claro, esencialmente se comporta un poco peor que O (n). Entonces, si n se duplica, el tiempo de ejecución se multiplica por un factor algo mayor que 2.
    2011-09-23 06: 44: 50Z

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

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

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

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

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

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

    
102
2011-09-13 03: 08: 33Z
  1. cdiggins, ¿qué pasa si tengo complejidad O (N /2), debería ser O (N) u O (N /2), por ejemplo, cuál es la complejidad si Voy a hacer un bucle en media cadena.
    2017-05-12 15: 08: 29Z
  2. @ Melad Este es un ejemplo de una constante (0.5) que se multiplica a la función. Esto se ignora, ya que se considera que tiene un efecto significativo para valores muy grandes de N.
    2017-05-18 19: 47: 55Z

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

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

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

Entonces, es posible que entiendas lo que significa "n 2 ", pero para ser aún más específico, juega con el pensamiento de que tienes un algoritmo de clasificación simple, el más simple; ordenamiento de burbuja. Este algoritmo debe revisar 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!
  • Compara 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 n 2 porque, debe mirar todos los elementos de la lista; hay elementos "n". Para cada elemento, miras todos los elementos una vez más, para comparar, esto también es "n", así que para cada elemento, miras "n" veces que significa n * n = n 2

Espero que esto sea tan simple como lo deseas.

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

    
79
2014-10-19 20: 47: 19Z
  1. para logN, consideramos que para el bucle que va de 0 a N /2, ¿qué pasa con O (log log N)? Me refiero a cómo se ve el programa? perdóname por habilidades matemáticas puras
    2015-09-30 10: 52: 49Z

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

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

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

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

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

    
53
2014-10-19 20: 48: 18Z

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

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

O(1):

No hay crecimiento. Independientemente de cuán grande sea el problema, puede resolverlo en el mismo período de tiempo. Esto es algo similar a la transmisión, en la que se necesita la misma cantidad de energía para transmitir en una distancia determinada, independientemente de la cantidad de personas que se encuentren dentro del rango de transmisión.

O (registro n):

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

O(n):

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

O ( n log n):

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

O(n2):

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

O(2 n ):

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

    
38
2014-03-10 06: 51: 52Z
  1. ¿Podría considerar una analogía diferente para O (1)? El ingeniero en mí quiere sacar una discusión sobre la impedancia de RF debido a obstrucciones.
    2016-03-10 23: 02: 28Z
  2. Usé la palabra "un poco" por una buena razón.
    2017-04-14 17: 12: 35Z

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), el tiempo /espacio aumentará a la misma velocidad que su entrada.

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

y así sucesivamente.

    
35
2014-10-19 20: 49: 11Z
  1. No se trata de espacio. Se trata de la complejidad que significa tiempo.
    2009-01-28 11: 35: 02Z
  2. Siempre he creído que puede tratarse de tiempo o espacio. pero no sobre ambos al mismo tiempo.
    2009-01-28 12: 58: 59Z
  3. La complejidad definitivamente puede ser sobre el espacio. Eche un vistazo a esto: en.wikipedia.org/wiki/PSPACE
    2010-08-08 15: 58: 49Z
  4. Esta respuesta es la más "simple" aquí. Los anteriores en realidad suponen que los lectores saben lo suficiente como para entenderlos, pero los escritores no son conscientes de ello. Ellos piensan que los suyos son simples y sencillos, que no lo son en absoluto. Escribir mucho texto con un formato bonito y hacer ejemplos artificiales sofisticados que son difíciles para las personas que no son miembros de la sociedad civil no es simple y simple, solo es atractivo para los populadores que en su mayoría son personas de la CS que votan. Explicar el término CS en un lenguaje sencillo no necesita nada de código y matemáticas. +1 para esta respuesta, aunque todavía no es lo suficientemente bueno.
    2013-05-29 12: 36: 01Z
  5. Esta respuesta comete el error (común) de suponer que f = O (g) significa que f y g son proporcionales.
    2015-04-03 04: 38: 41Z

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

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

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

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

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

El bien:

  •  Ɵ(...) Constante : el programa tarda el mismo tiempo en ejecutarse sin importar qué tan grande sea la entrada.
  •  Ɵ(exactlyThis) Logarítmica : el tiempo de ejecución del programa aumenta solo lentamente, incluso con grandes aumentos en el tamaño de la entrada.

Lo malo:

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

... y lo feo:

  •  O(log n) Exponencial El tiempo de ejecución del programa aumenta muy rápidamente incluso con aumentos moderados en el tamaño del problema; solo es práctico procesar pequeños conjuntos de datos con algoritmos exponenciales.
  •  O(n) Factorial El tiempo de ejecución del programa será más prolongado de lo que puede esperar, excepto los conjuntos de datos más pequeños y de apariencia más trivial.
31
2013-05-29 13: 51: 20Z
  1. También escuché el término Linearithmic - O(n^k) que se consideraría bueno.
    2013-05-29 18: 45: 06Z
  

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

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

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

Una explicación en inglés sencillo de What Big O Notation es:

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

    
31
2013-10-07 14: 02: 21Z

Una respuesta simple y sencilla puede ser:

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

    
27
2014-03-14 16: 25: 08Z

Ok, mis 2cents.

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

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

Di que el problema es "Encuentra la suma",

 O(k^n)

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

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

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

decirel problema es "encontrar la combinación",

 O(n!)

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

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

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

    
27
2014-10-19 20: 48: 48Z
  1. O(n log n) Espero que esto no volvería a preguntar.
    2013-06-18 14: 41: 28Z

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

Cuando decimos que un algoritmo es O (f (n)) estamos diciendo que el tiempo de ejecución (o el espacio requerido por ese algoritmo es siempre más bajo que algunos tiempos constantes de f (n).

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

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

    
25
2010-07-17 02: 29: 35Z
  1. También podemos usar la notación BigO para medir el caso más desfavorable y el caso promedio. en.wikipedia.org/wiki/Big_O_notation
    2011-09-05 16: 36: 05Z
  

" ¿Qué es una explicación simple en inglés de Big O? Con tan poco formal   Definición como posible y matemáticas simples. "

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

  

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

(* en un maravilloso sentido de tiempo de unidad libre !)
(** que es lo que importa, porque la gente siempre querrá más , si viven hoy o mañana)

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

  • Hablando en términos prácticos, el análisis de Big O es muy útil e importante porque Big O se enfoca directamente en la complejidad propia del algoritmo y ignora por completo /em> cualquier cosa que sea meramente una constante de proporcionalidad, como un motor de JavaScript, la velocidad de una CPU, su conexión a Internet y todas esas cosas que se convierten rápidamente en tan ridículamente obsoletas como un Modelo T . Big O se centra en el rendimiento solo de la manera que importa tanto para las personas que viven en el presente como en el futuro.

  • La notación Big O también destaca directamente el principio más importante de la programación /ingeniería de computadoras, el hecho que inspira a todos los buenos programadores a seguir pensando y soñando: la única manera de lograr resultados más allá de la marcha lenta de la tecnología es inventar un algoritmo mejor .

23
2013-08-24 06: 50: 03Z
  1. Que me pidan que explique algo matemático sin matemáticas es siempre un desafío personal para mí, como un bona fide Ph.D. Matemático y profesor que cree que tal cosa es realmente posible. Y como programador, espero que a nadie le moleste que me haya parecido que responder a esta pregunta en particular, sin matemáticas, es un desafío completamente irresistible.
    2013-08-15 02: 09: 07Z

Ejemplo de algoritmo (Java):

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

      return sum;
}

Descripción del algoritmo:

  • Este algoritmo busca una lista, elemento por elemento, en busca de una clave,

  • Iterando en cada elemento de la lista, si es la clave, devuelva True,

  • Si el bucle ha finalizado sin encontrar la clave, devuelva False.

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

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

  • Calcule cuánto tiempo (en relación con el tamaño de la entrada) toma el peor de los casos:

  • Peor caso: la clave no existe en la lista.

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

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

  • O (n) ~ Lineal

También hay Big-Omega, que representa la complejidad del caso óptimo:

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

  • Time (Best-Case) = 4

  • Tiempo: Ω (4) = O (1) ~ Instant \Constant

21
2018-05-18 10: 46: 20Z
  1. ¿De dónde viene tu constante 4?
    2014-07-04 13: 34: 45Z
  2. @ Iniciador del iterador de Rod, comparación del iterador, lectura del iterador, comparación de claves ... Creo que
        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;
          }
        }
    
    sería mejor
    2014-07-06 11: 04: 55Z

Big O

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

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

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

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

Pequeña o

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

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

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

  2. k (x) va a 0 cuando x va a a.

Ejemplos

  • sen x = O (x) cuando x → 0.

  • sin x = O (1) cuando x → + ∞,

  • x 2 + x = O (x) cuando x → 0,

  • x 2 + x = O (x 2 ) cuando x → + ∞,

  • ln (x) = o (x) = O (x) cuando x → + ∞.

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

Más ejemplos

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

  • O (n) + O (n 2 ) = O (n 2 ) cuando n → + ∞

  • O (O (n 2 )) = O (n 2 ) cuando n → + ∞

  • O (n 2 ) O (n 3 ) = O (n 5 ) cuando n → + ∞


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

    
18
2014-10-19 20: 50: 47Z
  1. Estás declarando "Big O" y "Small O" sin explicar qué son, enIngresar muchos conceptos matemáticos sin decir por qué son importantes y el enlace a wikipedia puede ser demasiado obvio en este caso para este tipo de pregunta.
    2014-01-11 14: 54: 41Z
  2. @ AditSaxena ¿Qué quieres decir con "sin explicar qué son"? Explicé exactamente lo que son. Es decir, "gran O" y "pequeña O" no son nada por sí mismas, solo una fórmula como "f (x) = O (g (x))" tiene un significado, que expliqué (en inglés simple, pero sin definir por supuesto todas las cosas necesarias de un curso de cálculo). A veces, "O (f (x))" se ve como la clase (en realidad el conjunto) de todas las funciones "g (x)", de manera que "g (x) = O (f (x))", pero esto es un paso adicional, que no es necesario para comprender los conceptos básicos.
    2014-01-11 18: 34: 54Z
  3. Bueno, está bien, hay palabras que no son simples en inglés, pero es inevitable, a menos que tenga que incluir todas las definiciones necesarias de Análisis matemático.
    2014-01-11 18: 38: 21Z
  4. Hola, #Alexey, eche un vistazo a la respuesta aceptada: es larga pero está bien construida y bien formateada. Comienza con una definición simple, sin necesidad de conocimientos matemáticos. Mientras lo hace, introduce tres palabras "técnicas" que explica de inmediato (relativo, representación, complejidad). Esto se realiza paso a paso al profundizar en este campo.
    2014-01-12 22: 44: 07Z
  5. Big O se usa para entender el comportamiento asintótico de los algoritmos por la misma razón que se usa para entender el comportamiento asintótico de las funciones (el comportamiento asintótico es el comportamiento cercano al infinito). Es una notación conveniente para comparar una función complicada (el tiempo o espacio real que ocupa el algoritmo) con los simples (cualquier cosa simple, generalmente una función de potencia) cerca del infinito, o cerca de cualquier otra cosa. Solo expliqué lo que es (dio la definición). Cómo calcular con O grande es una historia diferente, tal vez agregaré algunos ejemplos, ya que estás interesado.
    2014-01-13 17: 23: 47Z

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

    
18
2015-05-12 14: 02: 34Z

No estoy seguro de que esté contribuyendo más al tema, pero aún pensé que lo compartiría: una vez encontré esta publicación del blog para tener algunas explicaciones bastante útiles (aunque muy básicas) & ejemplos en Big O:

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

    
11
2013-01-15 20: 23: 20Z
  1. @ William ... y la gente tiende a morir de vejez, las especies se extinguen, los planetas se vuelven estériles, etc.
    2013-05-30 05: 52: 12Z

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

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

Ahora, hablemos de trabajo, tú y yo. La mayor parte del tiempo, no me gusta el trabajo. Te gusta el trabajo Puede ser el caso que lo haga, pero estoy seguro de que no.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ergh. ¡Eso suena a mucho trabajo!

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

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

Cuando el mazo está listo, pregunto: ¿cambié las cartas en ese pase? Si es así, debo hacerlo todo una vez más, desde la parte superior.

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

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

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

Big O, ayúdame!

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

¿Por qué dice n al cuadrado?

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

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

Ahora aquí es donde big O es nuestro amigo.

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

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

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

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

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

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

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

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

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

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

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

Tres: voy desde la última tarjeta hacia arriba y busco una tarjeta que sea más baja que la tarjeta de distribución.

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

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

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

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

¿Cómo se llama este tipo? ¡Se llama Quick Sort! Ese tipo fue hecho por un hombre llamado C. A. R. Hoare y lo llamó Ordenación rápida. ¡Ahora, Quick Sort se usa todo el tiempo!

La ordenación rápida divide las cubiertas grandes en las pequeñas. Es decir, divide las tareas grandes en las pequeñas.

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

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

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

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

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

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

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

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

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

Ahora que hemos terminado, ¡vamos a jugar!


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

    
11
2016-03-10 23: 03: 36Z

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

Entonces while (size-->0) significa, en inglés simple:

  

Si no tiene suerte cuando ejecuta A, puede tomar X (n) operaciones para   completa.

A medida que sucede, hay ciertas funciones (piense en ellas como implementaciones de X (n) ) que tienden a ocurrir con bastante frecuencia. Estos son bien conocidos y se pueden comparar fácilmente (ejemplos:

// 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;
}
, C, O( <some expression X involving n> ), 1, Log N, etc.)

Al comparar estos cuando se habla de A y otros algoritmos, es fácil clasificar los algoritmos según el número de operaciones que pueden (en el peor de los casos) requerir para completar.

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

    
9
2013-10-25 15: 11: 17Z

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

 N^2

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

 N!

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

 X(n)

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

 
statement;

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

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

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

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

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

9
2015-09-15 13: 52: 39Z

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

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

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

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

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

Referencia : http://carlcheo.com/compsci

    
9
2015-12-06 06: 01: 13Z

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

  

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

Y además

  

Los factores constantes son despreciables

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

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

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


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

    
8
2015-05-16 16: 02: 02Z
  

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

Nota muy rápida:

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

  • "Big O" hace dos cosas:

    1. Calcula cuántos pasos del método aplica tu computadora para realizar una tarea.
    2. ¿Facilita el proceso de comparación con otros para determinar si es bueno o no?
    3. "Big O 'logra los dos anteriores con
      for ( i = 0; i < N; i++ ) 
      {
      for ( j = 0; j < N; j++ )
        statement;
      }
      
      estandarizado.
  • Hay siete notaciones más utilizadas

    1. O (1), significa que su computadora realiza una tarea con el paso
      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 excelente, N ° 1 ordenado
    2. O (logN), significa que su computadora completa una tarea con
      void quicksort ( int list[], int left, int right )
      {
        int pivot = partition ( list, left, right );
        quicksort ( list, left, pivot - 1 );
        quicksort ( list, pivot + 1, right );
      }
      
      pasos, está en orden, No.2 Ordenado
    3. O (N), finalice una tarea con Notations pasos, es justo, Número de pedido 3.
    4. O (NlogN), finaliza una tarea con 1 pasos, no es bueno, Orden No.4
    5. O (N ^ 2), haga una tarea con logN pasos, es malo, Número de pedido 5.
    6. O (2 ^ N), haz una tarea con N pasos, es horrible, Orden No.6
    7. O (N!), haga una tarea con O(NlogN) pasos, es terrible, Orden No. 7

 ingrese la descripción de la imagen aquí

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

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

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

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

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

  • Resumen
    "Big O" describe el rendimiento del algoritmo y lo evalúa.

    o diríjalo formalmente, "Big O" clasifica los algoritmos y estandariza el proceso de comparación.

7
2018-04-13 13: 53: 42Z

La forma más sencilla de verlo (en un lenguaje sencillo)

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

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

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

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

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

 N!

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

En gran notación O, esto se escribe como

 O(N^2)

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

Volver a inglés

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

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

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

    
6
2016-09-15 14: 15: 12Z

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

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

  

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

     

Cualquier persona que haya leído Perlas de programación o cualquier otra ciencia informática.   libros y no tiene una base en Matemáticas habrán chocado contra una pared   cuando llegaron a los capítulos que mencionan O (N log N) u otros aparentemente   sintaxis loca Esperemos que este artículo te ayude a ganar un   comprensión de los conceptos básicos de Big O y logaritmos.

     

Como programador primero y matemático segundo (o tal vez tercero o   cuarto) encontré que la mejor manera de entender Big O era a   producir algunos ejemplosen codigo. Por lo tanto, a continuación hay algunas órdenes comunes de   crecimiento junto con descripciones y ejemplos cuando sea posible.

     

O (1)

     

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

 O(NlogN)      

O (N)

     

O (N) describe un algoritmo cuyo rendimiento crecerá linealmente y   en proporción directa al tamaño del conjunto de datos de entrada. El ejemplo   A continuación también se muestra cómo Big O favorece el peor desempeño.   guión; Se pudo encontrar una cadena coincidente durante cualquier iteración de la   para bucle y la función volvería pronto, pero la notación Big O   Siempre asuma el límite superior donde el algoritmo realizará la   Número máximo de iteraciones.

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

O (N 2 )

     

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

 
T(n)∈O(n)
     

O (2 N )

     

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

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

Logaritmos

     

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

     

La búsqueda binaria es una técnica utilizada para buscar conjuntos de datos ordenados. Funciona   seleccionando el elemento central del conjunto de datos, esencialmente el   mediana, y lo compara con un valor objetivo. Si los valores coinciden   volverá el éxito. Si el valor objetivo es mayor que el valor de   el elemento de sonda tomará la mitad superior del conjunto de datos y   Realiza la misma operación en su contra. Del mismo modo, si el valor objetivo   es más bajo que el valor del elemento de sonda que realizará la   Operación contra la mitad inferior. Continuará reduciendo a la mitad los datos.   establecer con cada iteración hasta que se haya encontrado el valor o hasta que pueda   Ya no se divide el conjunto de datos.

     

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

    
5
2018-10-31 17: 47: 18Z

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

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

Dependiendo de N y X, su algoritmo requerirá algunas operaciones, por ejemplo, en el caso de WORST, son las operaciones

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

    return false;
} 
.

Como Big-O no se preocupa demasiado por el factor constante (también conocido como 3), el Big-O de su algoritmo es

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;
}
. Básicamente, se traduce "la cantidad de operaciones que su algoritmo necesita para las peores escalas de caso con esto".     
4
2015-10-11 18: 00: 20Z

Definición: - La notación Big O es una notación que indica el rendimiento de un algoritmo si la entrada de datos aumenta.

Cuando hablamos de algoritmos, hay 3 pilares importantes Entrada, Salida y Procesamiento del algoritmo. Big O es una notación simbólica que dice si la entrada de datos aumenta en qué tasa variará el rendimiento del procesamiento del algoritmo.

Le animo a que vea este video de YouTube que explica Big O Notation en profundidad wiEjemplos de código.

 Algoritmo de pilares básicos

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

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

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

 Big O symbols

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

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

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

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

 3(N^2) + log(X)

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

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

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

 Clasificación de Bog O

Le recomendaría que viera este video de 10 minutos que discute Big O con código de muestra

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

    
4
2018-05-11 09: 43: 53Z
O(N^2 + log(X))
fuente colocada aquí