¿Qué es O en Big O?

Bueno, mi conjetura sería el orden, que coincide con wikipedia .

Editar: (mi propia (se agradecen las mejoras)) traducción del artículo de Wikipedia en alemán

La letra mayúscula O (en realidad un omicron mayúscula en ese momento) como símbolo del orden de (alemán: «Ordnung von») fue utilizada por primera vez por el teórico de números alemán Paul Bachman en el segundo número de su libro sobre teoría analítica de números apareció en 1894. La notación ganó popularidad debido al trabajo de Edmund Landau, otro teórico de números alemán, con quien esta nomenclatura está ampliamente asociada hoy en día, especialmente en el Terminología alemana.

Comentarios

• Si bien puede ser el caso al que muchos matemáticos se hayan referido como tal, originalmente no lo era. Si lee libros de teoría de números de principios del siglo XX, no encontrará tal explicación. Es lo que es y no puedo ‘ t leer alemán para averiguar cuál era su pensamiento sobre la notación.
• @Jonathan: Publicación actualizada.
• ¡Muy bonito! Busqué en todos mis libros de teoría de números y no pude ‘ encontrar una explicación de la O en ninguna parte. +1
• Yo ‘ siempre lo he pronunciado como orden de ya que decir O no significa mucho.
• ¡Muy informativo! pero aún así, ¿por qué los programadores la pronuncian como ‘ oh ‘?

«Grande» significa «mayúscula» y «O» significa orden, como en «orden de complejidad». Se llama así debido a la convención de escribir «orden de complejidad» como O (f (x)), por ejemplo, con una letra mayúscula «O» o una «O grande». Nadie habla mucho de él porque «todo el mundo» entiende lo que significa, y entenderlo realmente no le ayuda a entender el análisis de complejidad.

Para entender el análisis de complejidad, creo que el enlace publicado por topgun_ivard es un un buen lugar para comenzar. Un buen libro de texto introductorio que cubra estructuras de datos o algoritmos también podría ayudar.

Comentarios

• I ‘ lo siento, pero la notación de Bachmann-Landau fue inventada por un matemático alemán, por lo que no creo que le hubiera puesto el nombre de una palabra en inglés. De hecho, incluso si hubiera sido inventado por un matemático estadounidense, probablemente todavía habría sido nombrado por una palabra alemana, porque cuando se inventó (alrededor de 1920, creo), el idioma internacional de las matemáticas era el alemán. Además, no ‘ ni siquiera remotamente tiene algo que ver con la complejidad.
• @J ö rg: Sí, pero no ‘ Es solo Ordnung , que el artículo wiki alemán afirma ser el origen: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel, ¿podrías hacer un pequeño cambio en tu artículo para que pueda votar por ti? De hecho, tienes razón. Tienes que editar antes de que pueda votar.
• @Jonathan, ‘ no estoy seguro exactamente del cambio menor que deseas. ¿Puedes seguir adelante y hacer la edición que quieras? O bien, podríamos dejar que back2dos ‘ responda, parece que de todos modos podría haber terminado con la mejor respuesta debido a una excelente investigación 🙂
• Hm , interesante. En Suecia, Big Oh generalmente se llama » ordo » (del latín, bueno, orden) en lugar de » ordning » (la palabra sueca para orden).

Me gusta este artículo , ¡espero que a usted también le resulte útil!

Citando una sección del artículo:
Grandes letras griegas

La gran O a menudo se usa incorrectamente. Big O o Big Oh es en realidad la abreviatura de Big Omicron. Representa el límite superior de la complejidad asintótica. Entonces, si un algoritmo es O (n log n), existe una constante c tal que el límite superior es cn log n.

Θ (n log n) (Big Theta) está más estrechamente vinculado que eso. Tal algoritmo significa que existen dos constantes c1 y c2 tales que c1n log n < f (n) < c2n log n.

Ω (n log n) (Big Omega) dice que el algoritmo tiene un límite inferior de cn log n.

Hay otros, pero estos son los más comunes y Big O es el más común de todos. Tal distinción no suele ser importante, pero vale la pena señalarla. Después de todo, la notación correcta es la notación correcta.

¿Qué es Big O?

La notación Big O busca describir la complejidad relativa de un algoritmo reduciendo la tasa de crecimiento a la clave factores cuando el factor clave tiende hacia el infinito. Por esta razón, a menudo escuchará la frase complejidad asintótica. Al hacerlo, se ignoran todos los demás factores. Es una representación relativa de la complejidad.

¿Qué no es Big O?

Big O no es una prueba de rendimiento de un algoritmo. También es teórico o abstracto en el sentido de que tiende a ignorar otros factores. La complejidad del algoritmo de clasificación generalmente se reduce al número de elementos que se clasifican como factor clave. Esto está bien, pero no tiene en cuenta problemas como:

Uso de memoria: un algoritmo puede usar mucha más memoria que otro. Dependiendo de la situación, esto podría ser desde completamente irrelevante hasta crítico; Costo de la comparación: puede ser que comparar elementos sea realmente costoso, lo que potencialmente cambiará cualquier comparación del mundo real entre algoritmos; Costo de los elementos móviles: copiar elementos suele ser barato, pero no es necesariamente el caso; etc.

Comentarios

• Simplemente enlazar un artículo no es ‘ t demasiado útil. ‘ suele ser una buena idea parafrasear o citar la sección que le parezca especialmente relevante para el hilo.
• ¿Son realmente necesarios los votos negativos? El artículo que vinculó es muy relevante y, en mi humilde opinión, bastante útil.Mientras tanto, la respuesta más votada es un enlace a un artículo de Wikipedia. +1 para compensar la hipocresía de la mente colmena.
• -1, porque el artículo, aunque es un artículo muy agradable y bien escrito, no ‘ No tengo nada que ver con la pregunta.
• @Jorg, nunca dije que el artículo resolvería el problema, pero lo compartí porque lo encontré útil cuando estaba mirando estos conceptos.
• @topgun_ivard: Entonces, ¿qué sucede si se convierte en un enlace muerto? Parafrasear permite 1) que la audiencia de este hilo obtenga una versión de notas de Coles de su enlace (el tiempo es dinero), y 2) asegura que su publicación no se vuelva irrelevante en un enlace muerto.

EDITAR: Resulta que estoy equivocado. Sin embargo, tal vez esto ayude a alguien a mantener sus símbolos rectos, así que no voy a borrarlo.

En realidad, es no la letra latina Oh , es la letra griega Omicron . Desafortunadamente, esos dos tienen exactamente el mismo glifo, por lo que, con el tiempo, la versión original se corrompió, y ahora es solo Oh .

La elección del símbolo en realidad no tiene ningún significado en particular, fue elegido como un dispositivo mnemónico :

• Omicron tiene las letras MICRO y la semántica del símbolo Omicron significa aproximadamente «más pequeño que»
• Omega tiene las letras MEGA , y la semántica del símbolo Omega significa aproximadamente «más grande que»
• Theta (Θ) se parece un poco a un signo igual , y la semántica del símbolo Theta significa aproximadamente «igual a»

Eso es todo. No tiene un significado real, es solo un juego de palabras, si Will, para ayudarte a recordar la semántica más e fácilmente.

Comentarios

• Si bien me encantaría creer en tu proposición mnemotécnica (es una idea realmente genial), voy a necesitar ver alguna prueba de que esta es la verdadera intención original de Bachmann. Proporciónelo y ‘ haré +1 en usted.
• @Jonathan Henson: Aparentemente, el Prof. Knuth me engañó 🙂

«f (x) es grande-oh de g (x)»

Es una forma matemática de predecir el crecimiento de funciones.

Sean fyg funciones del conjunto de enteros o del conjunto de números reales al conjunto de números reales. Decimos que f (x) es O (g (x)) si hay constantes C y k tales que | f (x) | < = C | g (x) | donde sea x> k.

Leerías esto como «f (x) es un gran-oh de g (x)»

El gran-O a veces se llama símbolo de Landau después el matemático alemán Edmund Landau. No creo que represente nada más allá de eso. También tienes notaciones similares de gran Omega y gran Theta. Los símbolos son tan arbitrarios como siempre, usar theta para denotar los ángulos en tus triángulos en tu geometría plana de la escuela secundaria class.

Corrección @ back2dos ha proporcionado una explicación satisfactoria de la O como referencia al orden. Excelente Job. Vea su respuesta.

Donald Knuth lo aplicó al estudio de la complejidad de los programas de computadora.

Si desea encontrar la razón por la que se usó la notación, debe leer

«Analytische Zahlentheorie» de Paul Bachmann de 1892

ACTUALIZACIÓN: Intento limpiar mi respuesta y ser más preciso

La notación Big O es una forma de caracterizar funciones de acuerdo con sus tasas de crecimiento. significa orden (el primer orden es n, el segundo orden es n-cuadrado, etc.). Y si no soy equivocado, este sería el peor de los casos para un tiempo de ejecución de métodos (o almacenamiento) dados N elementos. Cuanto mayor sea el orden, peor será el rendimiento del método.
Por ejemplo, buscar un registro en una matriz es O (1) (creo en alguna implementación de tablas hash que también es el caso). Agregar un valor al final de una lista de enlaces sería O (N) porque debe llegar al final de la lista antes de poder agregar el elemento, etc.

Esta respuesta debería ser un poco más correcta que mi primer intento 🙂

Comentarios

• -1 porque esto es simplemente antiguo incorrecto Y respondió una pregunta separada de la que se hizo. La pregunta era por qué se usa la letra » O «, no » cómo ¿La notación O funciona? «. Sin embargo, ‘ se equivoca acerca de cómo funciona Big-oh … recorrer una matriz es O (n) donde n es el tamaño de la matriz, no O (1) . La notación no tiene nada que ver con » ciclos » de un algoritmo … es ‘ una medida del límite superior del tiempo de ejecución de un algoritmo.
• No quiero discutir con usted aquí, sino que ‘ es lo que quise decir. ¿Qué significa tiempo de ejecución, verdad?Bueno, el tiempo de ejecución está determinado por lo que se debe procesar en la máquina. Supongo que uso el ciclo generosamente aquí. Por ciclo, supongo que debería haber dicho iteración o algo así. Sin embargo, tiene razón sobre el límite superior, no determina el promedio. Por lo tanto, acepto la degradación.