¿Qué es O en Big O?

¿Qué es Big y O en notación Big O? He leído las definiciones y no dice qué se pronuncia O como 'oh'. Por ejemplo, entiendo que O (n) es la complejidad de un algoritmo lineal donde n podría ser el número de operaciones. pero que es un O ?

Bueno, mi suposición sería el orden, que coincide con wikipedia .

Editar: (mi propia (cualquier mejora apreciada)) 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 la segunda edición de su libro sobre teoría analítica de números. en 1894. La notación ganó popularidad debido al trabajo de Edmund Landau, otro teórico de números alemán, a quien esta nomenclatura se asocia ampliamente hoy, especialmente en la terminología alemana.

"Grande" significa "capital" y "O" significa orden, como en "orden de complejidad". Llamado así por 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 eso porque 'todos' entienden lo que significa, y entenderlo realmente no ayuda a comprender el análisis de complejidad.

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

O representa el orden.

Fue introducido originalmente por el matemático alemán Paul Bachmann en el segundo volumen de sus libros sobre teoría de números Die Analytische Zahlentheorie , publicado en 1894 (p. 401) . Él observa, después de una fórmula donde primero usa la notación:

(...) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung en Bezug auf n die Ordnung von n nicht überschreitet (...)

Mi traducción:

(...) donde con la notación O (n) indicamos una magnitud cuyo orden con referencia a n no excede el orden de n (...)

En contraste con lo que otros han dicho, nada en su texto indica que este sea de hecho un omikron de capital griego. Utiliza muchos caracteres griegos y latinos, por lo que realmente no hay forma de saberlo. Dado su uso continuo de "Ordnung n log n ", etc. en el texto, está claro que significa "Ordnung" (alemán para "orden" si había alguna duda) en cualquier caso, pero eso podría dejar abierto el uso de un elegante griego O.

Sin embargo, el origen del omikron es más probable que sea un retónimo debido a Donald Knuth, quien introdujo los símbolos omega (Ω) y theta (Θ) para conceptos relacionados en su artículo Big Omicron y Big Omega y Big Theta , o posiblemente Hardy y Littlewood que introdujo un símbolo omega anteriormente.

¡Me gusta este artículo , esperando que lo encuentres útil también!

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

Big O a menudo se usa mal. 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 unido que eso. Tal algoritmo significa que existen dos constantes c1 y c2, de modo 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. Dicha distinción generalmente no es importante, pero vale la pena señalar. La notación correcta es la notación correcta, después de todo.

¿Qué es Big O?

La notación Big O busca describir la complejidad relativa de un algoritmo reduciendo la tasa de crecimiento a los factores clave 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 nocional o abstracto, ya que tiende a ignorar otros factores. La complejidad del algoritmo de clasificación generalmente se reduce a la cantidad de elementos que se ordenan como factor clave. Esto está bien, pero no tiene en cuenta problemas como:

Uso de memoria: un algoritmo podría 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 mover elementos: copiar elementos suele ser barato, pero este no es necesariamente el caso; etc.

"f (x) es grande-oh de g (x)"

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

Supongamos que f y g son funciones del conjunto de números enteros o del conjunto o 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 x> k.

Leerías esto como "f (x) es grande-oh de g (x)"

El big-O a veces se llama un símbolo de Landau después del matemático alemán Edmund Landau. No creo que signifique nada más que eso. También tiene las notaciones similares big-Omega y big-Theta. Los símbolos son tan arbitrarios como siempre usar theta para denotar los ángulos en sus triángulos en su clase de geometría plana de la escuela secundaria.

Correction @ back2dos ha proporcionado una explicación satisfactoria para el O en referencia al pedido. Gran trabajo. Ver su respuesta.

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

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

"Analytische Zahlentheorie" de Paul Bachmann desde 1892

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

En realidad, es que 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 particular, se eligió como un dispositivo mnemónico :

• Omicron tiene las letras MICRO, y la semántica del símbolo Omicron significa "más pequeño que"
• Omega tiene las letras MEGA y la semántica del símbolo Omega significa "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. No tiene un significado real, es solo un juego de palabras, si quieres, para ayudarte a recordar la semántica más fácilmente.

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

La notación Big O es una forma de caracterizar las funciones de acuerdo con sus tasas de crecimiento. La O significa orden (el primer orden es n, el segundo orden es n-cuadrado, etc.). Y si no me equivoco, este sería el peor de los casos para un tiempo de ejecución de métodos (o almacenamiento) dados N elementos. Cuanto mayor es el orden, peor es el 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 :)