¿Qué es la notación O grande? ¿Y deberían saberlo los programadores principiantes?

La notación Big-O es un medio para analizar el comportamiento asintótico. Es idea del análisis matemático. Describe el comportamiento limitante de una función.

En ingeniería de software, se utiliza para analizar el comportamiento asintótico de un algoritmo dado (función en términos matemáticos). Puede analizar el tiempo de ejecución (¿cuánto tiempo se tarda en calcular una respuesta?) O el almacenamiento (¿cuánta memoria se tarda en calcular una respuesta?)) O algún otro comportamiento.

Muy a menudo, cuando un ingeniero de software dice “cuál es el Big-O de …”, están hablando del tiempo de ejecución aymptótico en términos de la entrada. Dada una entrada de tamaño n, ¿cuál es el tiempo necesario para calcular la respuesta? ¿Es sublineal (por ejemplo, O (ln n)), lineal (es decir, O (n)) o superlineal (por ejemplo, O (n ^ 2))? Tener esta información le permite comprender cómo funcionará el algoritmo a medida que aumenta su entrada.

Personalmente, no esperaría que un programador conociera necesariamente este concepto, pero esperaría que un informático lo supiera. Es decir, si han estudiado formalmente ciencias de la computación, entonces deberían estar absolutamente conscientes del concepto. Incluso si han aprendido ingeniería de software de manera informal, un buen ingeniero de software debería ser capaz de explicar cómo un algoritmo escalará el tamaño de la entrada.

Mi opinión es que cualquiera que escriba código para ganarse la vida debe comprender la idea de Big O. No es necesario que pueda presentar pruebas matemáticas rigurosas que indiquen que un fragmento de código es O (lo que sea).

Para fines prácticos de ingeniería, Big O básicamente comprende la relación entre el tamaño de un problema y el tiempo que tomará resolverlo.

O (1) significa que el tiempo que lleva resolver un problema no varía según el tamaño del problema. Ejemplos:

1. agregar dos enteros de tamaño fijo (por ejemplo, 8 bits, 32 bits, 64 bits, 128 bits, lo que sea) juntos (esto excluye los enteros que pueden ser de tamaño arbitrario, como los proporcionados en las bibliotecas BigInteger), (se aplica igualmente a otras funciones aritméticas simples en valores de tamaño fijo)
2. agregar un elemento a un hashset o buscar si un elemento ya está en un hashset (suponiendo que no haya colisiones),
3. recuperar el enésimo elemento de una matriz o colección basada en una matriz,
4. empujando o haciendo estallar un elemento dentro o fuera de una pila,
5. poner en cola o eliminar un artículo de una cola,
6. insertar un nodo o conjunto de nodos en una lista vinculada siempre que ya tenga los nodos a los que deberá conectarlos.
7. Comparar dos valores de tamaño fijo (como dos enteros)
8. Mover un valor a otra ubicación en la memoria donde el espacio ya está asignado

O (log n) significa que el tiempo que llevará completar el algoritmo aumentará logarítmicamente a medida que aumente el tamaño del problema. Obviamente, esto no es tan bueno como O (1) pero sigue siendo bastante bueno.

Así que imagine que una función foobar (x) necesitará realizar operaciones log (x.Size) para obtener su valor de retorno. Suponga que cada operación toma .1 microsegundos. Entonces (redondeando hacia arriba) si x es tamaño 1000, entonces log2 (1000) = 10, entonces la cantidad de tiempo (en un mundo perfecto) para completar será de 1 microsegundo (10 * .1 microsegundos). Ahora, ¿qué tan grande debería ser x para duplicar ese tiempo de 1 microsegundo? Bueno, log2 (x) = 20 – resuelve para x. Resulta que la respuesta es 1,000,000.0. Por lo tanto, el tamaño del problema tuvo que aumentar mil veces el tiempo que tardó en duplicarse .

Ejemplos de operaciones O (log n)

1- encontrar un número en una matriz ordenada usando búsqueda binaria o un árbol de búsqueda binaria

2- insertar o eliminar un elemento de un árbol de búsqueda binario equilibrado

3- usando el algoritmo de euclides para encontrar el mcd de dos enteros de tamaño fijo

O (n) –

Estas operaciones hacen que la cantidad de tiempo crezca linealmente con el tamaño del problema. Muy claro.

Ejemplos

1- bucle sobre una serie de enteros

2- insertar un elemento en una matriz de enteros (en un lugar que no sea el principio o el final, o en cualquier lugar cuando la matriz haya alcanzado su capacidad)

3- ubicar el enésimo elemento en una lista vinculada

4- enumerar todos los elementos en un árbol de búsqueda binario balanceado

O (n log n)

Estas operaciones llevan más tiempo que las operaciones lineales, pero no tan horriblemente. El ejemplo clásico es un algoritmo de clasificación eficiente, como Heapsort.

O (n ^ 2)

El tiempo aquí crece polinomialmente con respecto al tamaño del problema. Para tamaños de problema razonables, estos problemas pueden resolverse con computadoras modernas. Para grandes cantidades, puede llevar bastante tiempo.

Ejemplo: bucles anidados de tamaño n.

Sin embargo, señalaré que una de las cosas más importantes que eliminé de mi estudio formal de CS es que a menudo, aunque no siempre, se puede superar el tiempo polinómico. Por ejemplo, el tipo de burbuja (el tipo de clasificación que probablemente se te ocurrió cuando eras niño tratando de descubrir cómo ordenar elementos en una matriz) es O (n ^ 2). Pero un tipo más eficiente puede darle O (n log n) en su lugar.

O, por ejemplo, escriba una función que dado un entero n devuelve n agregado por todos los enteros anteriores a uno. Por ejemplo 5 => 5 + 4 + 3 + 2+ 1 => 15. La forma en que se te ocurre inmediatamente toma O (n). Pero se puede hacer en O (1) si conoce el algoritmo correcto o puede derivarlo de su conocimiento matemático. Cosas ordenadas.

De todos modos, realmente no hago este análisis en mi código muy a menudo porque la mayor parte de mi trabajo está fuertemente vinculado a E / S de todos modos. Eso no significa que no sepa la diferencia entre encontrar un número en una matriz sin clasificar frente a un hashset. O la complejidad temporal básica de las operaciones en la biblioteca .NET que uso con frecuencia. Creo que eso es todo lo que la mayoría de los programadores necesitan saber.

Digamos que usted está conduciendo un Ferrari y tiene que viajar al hotel que se encuentra en algún lugar de una carretera (cuadrícula 1D), no sabe dónde. La carretera tiene N km de largo y por cada km que su automóvil viaja consume 0,5 l de combustible. Entonces, en el peor de los casos, el hotel estará ubicado al final de la carretera, por lo que su automóvil al máximo tomaría 0.5 * NL de combustible.
Ahora, digamos que en lugar de conducir un Ferrari , manejaste un vehículo más eficiente en combustible, como un CBR 250. Ahora tu bicicleta consume solo 0.1 L de combustible por cada km que conduces, y ahora estás buscando el mismo hotel en la misma carretera , y en el peor de los casos, tomará aproximadamente 0.1 * NL de combustible.

Aquí la cantidad de combustible consumido era un indicador de eficiencia. Cuanto menor sea el combustible que consumió, mejor. Pero tenga en cuenta que aunque la bicicleta consume menos combustible que el automóvil, el combustible que consumen ambos sigue siendo proporcional N

• Combustible consumido por el automóvil ∝ N
• Combustible consumido por la bicicleta ∝ N

Ahora, con el nombre de vehículos, deje que el hotel se ubique en algún lugar de las carreteras M que tienen N km de largo y son paralelas entre sí (cuadrícula 2D):
Entonces, en el peor de los casos, el CBR consumirá 0.1 * N * M, y el Ferrari consumirá 0.5 * N * M

• Combustible consumido por el automóvil ∝ N * M
• Combustible consumido por la bicicleta ∝ N * M

En ambos casos, lo único que nos importa es cuántos kilómetros tenemos que buscar.
No nos importa si el Ferrari / CBR consume 0.01 L / km o 100 L / km

Si ahora traducimos esto con respecto a las computadoras, el combustible indica el tiempo y la longitud del camino / número de caminos indica el tamaño de entrada. Todo lo que queremos saber es cuánto tiempo llevará nuestra computadora con respecto al tamaño de entrada.

No nos importa qué lenguaje de programación se usa o qué procesador se usa, todo lo que nos importa es: “En el peor de los casos, el tiempo que toma el programa es proporcional a qué”.

Esta notación es famosa notación Big-Oh. Entonces, si decimos que este programa toma tiempo O (N), esencialmente estamos diciendo que el tiempo que toma el programa es proporcional a N.

Esta notación es extremadamente útil porque no nos importa si toma 0.02 segundos leer un número entero en Python en lugar de 0.002 segundos en C ++. Lo único que nos importa es cuánto tiempo lleva leer una matriz en general, independientemente de todos los factores. Piénselo más como una ecuación generalizada.

Espero que haya sido una explicación suficientemente decente en cuanto a qué es la notación Big-Oh.
Aclamaciones.

Para complementar las respuestas ya proporcionadas, aquí hay algunos gráficos.

Gracias a la notación Big O y ¿Cuál es una explicación sencilla en inglés de la notación “Big O”?

Puede encontrar mucho sobre las grandes O en los libros de texto / cursos en línea, pero déjeme explicarlo en palabras simples.

Primero definamos la complejidad de los algoritmos: es la medida de parámetros como el tiempo, el espacio, etc., lo que define cuán eficiente es un programa de computadora. Está claro que un programa eficiente toma comparativamente menos tiempo y menos espacio para ejecutarse.

Ahora surge la pregunta de cómo comparar el tiempo de ejecución / espacio de los programas. Medimos los parámetros en función de las variables de entrada utilizando la función O grande. Esta función no dice exactamente cuánto tiempo en minutos / seg llevará el programa ejecutar, sino aproximadamente cuántos pasos tomará mientras se ejecuta (porque el tiempo de ejecución es proporcional al número de pasos). En general, solo se considera un tamaño de entrada grande para el análisis de complejidad y comprenderá la razón más adelante cuando comience a codificar.

Ejemplo simple: for (int i = 1; i <= n; i ++) {print (i); }

print (i) -> toma tiempo constante (digamos = c). Se ejecuta n veces, así que el tiempo total = c * n, si n es una variable de entrada que se puede variar, entonces la complejidad de este programa es O (c * n) pero como solo necesitamos expresión de proporcionalidad, escribimos ignorando todas las constantes, O ( norte)

Ejemplo 2: for (int i = 0; i

Si(…) {………}

para (int j = 1; j <= n; j ++) {

int x = i * j; }

}

digamos si (…) toma tiempo c1 y x = i * j toma tiempo c2. Así, el tiempo total = c1 * n + c2 * n * n. Aquí n * n es el término dominante porque si n es muy grande, [matemática] n ^ 2 >> n [/ matemática]. Por lo tanto, la complejidad general es O (n ^ 2).

Dado que el O grande es una función del tamaño de entrada, podemos observar al observar la función que cómo el aumento de entrada afectará el tiempo de ejecución. BigO si es un concepto muy importante y cada principiante debe aprender a analizar los algoritmos porque, de lo contrario, ¿cómo sabrá sobre el tiempo de ejecución de su propio código? En la codificación competitiva, son posibles varias soluciones para el mismo problema, pero la solución que tiene una mayor complejidad se agota, es decir, el juez no aceptará su solución. Por lo tanto, uno debe tener el conocimiento suficiente para decidir sobre la solución correcta.

Puede leer sobre las complejidades de los algoritmos para principiantes, como la combinación de clasificación, clasificación de burbujas, búsqueda lineal y binaria, clasificación rápida, tamiz de Eratóstenes, etc. En cuestión de días podrá calcular la complejidad de cualquier programa usted mismo.

En base a esta respuesta en Software Engineering Stack Exchange, la ‘O’ en notación asintótica representa el ‘Ordnug’ alemán que se traduce como ‘orden’. La notación asintótica se usa en el análisis de complejidad de algoritmos para referirse a la complejidad del peor de los casos (en cualquier dimensión dada) de un algoritmo. En otras palabras, se refiere al orden de tiempo, espacio, etc. que toma un algoritmo desde el momento en que comienza a ejecutarse hasta que termina. La ‘n’ se refiere al espacio de entrada del algoritmo.

Después de familiarizarse con las construcciones de programación básicas, es importante aprender no solo la ‘notación O grande’ sino también la estructura de datos básica y el análisis y diseño de algoritmos (que incluye la notación) para ayudarlo a comprender el material que encontrará cuando trabaje sobre cualquier cosa que tenga que ver con el software y el desarrollo de estructuras de datos y algoritmos eficientes. A menudo se usa para decidir una solución a partir de un conjunto de opciones. Como ejemplo, si observa el historial de los planificadores en la comunidad Linux, uno de los principales factores decisivos para lo que sería un “mejor” planificador siempre ha sido la complejidad. Los dos últimos planificadores predeterminados incluso fueron nombrados por sus complejidades de tiempo en el peor de los casos, O (n) y O (1).

¿Qué es la notación O grande? ¿Y deberían saberlo los programadores principiantes?

Me gano los juegos para ganarme la vida, principalmente dedicando mi tiempo a diseñar y programar y liderar proyectos de desarrollo y gestión.

No sé qué es la notación Big-O. Es una sola búsqueda en Google.

Pero no necesito saberlo y estoy ocupado tratando de terminar rápidamente esta respuesta antes de que termine la compilación.

Aquellos que lo saben e insisten en que es absolutamente necesario: google a posteriori y a priori .

Si tuviera que usar un esmoquin y visitar una de esas pretenciosas convenciones donde la gente habla sobre programación, podría buscar dos docenas de términos como estos y arrojarlos. Podría descubrir que he estado usando los mismos métodos descritos durante años.

Pero no me interesa sostener una copa de champán y posar en convenciones y galas.

Trabajo, paso tiempo con la familia, juego y hago otras actividades.

No, tampoco escribo descripciones elaboradas de lo que voy a hacer cuando escribo código solo. Qué horrible hábito. ¿No hay pruebas unitarias? El horror.

Pero lo que puedo hacer es terminar un juego por una fracción del costo que le costaría a un equipo de estudiantes de CS. Quién sabe, incluso podría ser mejor y más confiable, o no.

Lo que me encanta de la programación es que no es contabilidad. No necesita un certificado ni una pila de libros para decirle cómo hacer su trabajo. Se le permite usar la cabeza y trabajar de manera inteligente.

Dudo seriamente que conocer el término CS para un método o práctica que estoy usando me haga más rápido.

La notación Big O (O que significa Orden), también llamada símbolo de Landau (porque Landau es la razón principal detrás de su popularidad), es un simbolismo utilizado en matemáticas para describir el comportamiento asintótico de las funciones. Básicamente, nos dice qué tan rápido crece o disminuye una función. Ha sido utilizado por matemáticos durante mucho tiempo en teoría de números, matemática discreta y otros campos de estudios.

Para la definición formal, suponga que f (x) yg (x) son dos funciones definidas en algún subconjunto de los números reales. Escribimos [math] f \ left (x \ right) = O \ left (g \ left (x \ right) \ right) [/ math] si y solo si existen constantes N y C tales que [math] \ left El | f \ left (x \ right) \ right | \ le C \ left | g \ left (x \ right) \ right | [/ math] para todos [math] x> N. [/mates]

Las personas están motivadas para usar la notación O porque simplifica significativamente los cálculos porque nos permite ser descuidados, pero de manera satisfactoriamente controlada.

Más tarde, DE Knuth notó esta característica de la notación O, quien propuso el uso de O en Ciencias de la Computación Teórica.

Sobre la base de los temas discutidos aquí, propongo que los miembros de SIGACT y los editores de revistas de informática y matemáticas, adopten las [matemáticas] O [/ matemáticas] , [matemáticas] \ Omega [/ matemáticas] , [matemáticas] \ Theta [/ math] y anotaciones como se definió anteriormente, a menos que se pueda encontrar una mejor alternativa razonablemente pronto.

-DE Knuth, BIG OMICRON Y BIG OMEGA Y BIG THETA

Noticias SIGACT, 1976

Por lo tanto, ahora la notación O se usa ampliamente en el estudio de algoritmos y ciencias de la computación teórica para denotar la eficiencia computacional de un algoritmo o proceso porque hasta ahora no se ha encontrado una alternativa mejor.

Expresa el límite superior o el peor de los casos de cualquier proceso matemático o algoritmo en función del tamaño de entrada y nos ayuda a apreciar la importancia de mejores algoritmos en el campo de la computación.

Al escribir la solución a cualquier problema, es muy importante saber qué tan rápida es su solución. Es muy fácil encontrar un algoritmo para resolver un problema, pero si está escribiendo con una buena complejidad de tiempo / espacio, debe centrarse en eso. Básicamente le dice que cómo responde su código a los cambios en el tamaño de entrada, como cómo cambia el tiempo de procesamiento de un algoritmo a medida que el tamaño del problema se vuelve extremadamente grande. Mira este articulo :

La importancia de los algoritmos

Si tiene alguna función, la notación O que debe leer como Orden de dicha función, significa que dos funciones diferentes con los mismos órdenes toman la misma notación O cuando las describe. En palabras simples, esta notación muestra hasta qué límite crece la función cuando el argumento tiende a algún número o incluso infinito. La descripción asintótica significa “toma lo más cerca posible de eso, pero no toma este valor exacto y no va más allá”. Tal describe el límite más grande posible para algo. Tome la noción de que tal límite a la función se puede abordar desde dos lados. Describamos tal límite como un subconjunto de números S, que lo contiene. Entonces, el límite superior U será un subconjunto de ese S donde cada elemento es más grande o igual que el subconjunto S, es decir, el límite desde arriba se acercó. El límite inferior L es el mismo pero menor o igual que todos los elementos de S, es decir, el límite abordado desde abajo. Así que esto se trata de algún límite, útil para establecer algunos límites apropiados en la complejidad de la computación, cantidades de tiempo requeridas, etc. para algunos procesos no descritos y complejos de funciones descritas. Espero que haya logrado hacerlo en palabras simples

¿Qué es la notación O grande?

Puedo ser realmente técnico aquí, pero estás pidiendo una respuesta que se aplique a un programador principiante. La notación Big O es una forma rápida (matemática) de explicar el aumento (peor de los casos) en el uso de un recurso en relación con la entrada que se proporciona. La mayoría de las veces he visto a Big O medir el espacio de tiempo de ejecución y el espacio de uso de memoria.

Tendemos a usar cosas como O grande de n-cuadrado, lo que significa que si duplicamos la entrada, nuestro peor caso tomaría cuatro veces la cantidad de recursos. Para cosas pequeñas (y algunas cosas de UI) eso realmente no importa porque más rápido que un parpadeo sigue siendo más rápido que un parpadeo, incluso si uno es 100 veces más lento que el otro. Aquí está la cosa, Big-o te pregunta: “¿Qué tan mal se escala?”

Por ejemplo, supongamos que está buscando en una lista de elementos un valor específico. Ahora, si la lista de elementos ya está ordenada, puede hacer una búsqueda binaria. En una búsqueda binaria, tiende a eliminar aproximadamente la mitad de los elementos de su búsqueda cada vez que hace una comparación (también conocido como verificar un elemento), esto lleva a un tiempo de ejecución de O (log (n)) donde ‘n’ es el número de artículos en la lista. También necesitará tres rastreadores de índice: índice actual, mín. índice y máx. índice. Esto le dará un espacio de ejecución (o huella de memoria) de O (1). Como dije antes, le pedimos que aumente el uso de los recursos, no el uso real de los recursos. Con un tiempo de búsqueda de O (log (n)), duplicar el número de elementos aumentará el número máximo de comparaciones en 1, pero la cantidad de memoria que solicitamos no aumentó en absoluto, de ahí el espacio de ejecución de O (1 )

Cambiemos un poco las condiciones del problema y digamos que la lista no está ordenada y que el elemento que estamos buscando NO está dentro de la lista. ¿Cómo descubriría la computadora que el elemento que estamos buscando no está dentro de la lista sin verificar cada elemento? No lo hará, y debido a que necesitamos buscar en cada elemento (que es el peor de los casos) ahora tenemos un tiempo de ejecución de O (n) donde ‘n’ es el número de elementos en la lista. En cuanto al espacio de ejecución, esta vez solo necesitamos un índice para realizar un seguimiento de nuestra ubicación actual. Podemos agregar tantos elementos como queramos a la lista, pero todavía necesitamos solo un índice, por lo que el espacio de ejecución es O (1).

Los programadores principiantes deberían ahora al respecto:

Bueno sí. Lo que un programador principiante debe saber sobre esto está sujeto a debate, pero al menos debe ser consciente de lo que significa.

Sí, un programador absolutamente debe saber sobre cosas que son básicamente Ciencias de la Computación del primer año.

Y sí, específicamente necesitan saber sobre la complejidad del tiempo / espacio. Simplemente no puedo confiar en tu trabajo si no lo haces.

Aquí hay una buena referencia: Big O Notation | Pastel de entrevista.

Principiante, como en la suciedad principiante? No, no necesitas saber sobre la gran O tan temprano. Pero si está en la etapa en la que sabe una o dos cosas sobre la codificación, la O grande sería extremadamente útil y, en algunos casos, extremadamente importante saber, al menos, la premisa básica de lo que es.

Hay muchas referencias disponibles para grandes O. Una búsqueda en Google te llevaría a las mejores explicaciones posibles. Siéntase libre de comentar si tiene problemas para aprenderlo.

Una respuesta incompleta y poco precisa que con suerte le dará la idea: es una medida que le permite saber qué sucede con la cantidad de tiempo que tomará algo según la cantidad de cosas que le dé.

Por ejemplo, O (n) significa que, dados n elementos, el tiempo necesario será proporcional a n. Eso significa que si duplica el número de elementos, duplica el tiempo que lleva. (Un ejemplo podría ser un método que toma una lista de elementos y los imprime).

O (n ^ 2) significa que si duplica el número de elementos, cuadruplicará el tiempo que lleva. (Un ejemplo podría ser un tipo ingenuo).

O (1) significa que no importa cuántos elementos tenga, el tiempo requerido no cambia. (Un ejemplo podría ser un método que imprime el número de elementos en una colección, donde la colección realiza un seguimiento de su recuento y no tiene que contar los elementos).