¿Qué es O en Big O?

21

¿Qué es Big y O en la notación Big O? He leído las definiciones y no dice qué es O pronunciado 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 ¿qué es una O ?

    
pregunta Karen15 13.09.2011 - 20:03

7 respuestas

31

Bueno, mi conjetura sería 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 ícono en mayúscula en ese momento) como   el símbolo para el orden de (en alemán: "Ordnung von") fue utilizado por primera vez por el   El teórico alemán Paul Bachman en el segundo número de su libro.   La teoría de los números analíticos apareció en 1894. La notación ganada   popularidad debido a la obra de Edmund Landau, otro número alemán   Teórico, con quien esta nomenclatura está ampliamente asociada hoy en día,   especialmente en la terminología alemana.

    
respondido por el back2dos 13.09.2011 - 20:08
15

"Grande" significa "capital", y "O" significa orden, como en "orden de complejidad". Llamado 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 eso porque "todos" entienden lo que significa, y entenderlo no ayuda realmente 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 cubra estructuras de datos o algoritmos también podría ayudar.

    
respondido por el Ethel Evans 13.09.2011 - 20:25
11

O significa orden.

Originalmente fue presentado por el matemático alemán Paul Bachmann en el segundo volumen de sus libros sobre números. Teoría Die Analytische Zahlentheorie , publicada en 1894 (pág. 401) . Señala, después de una fórmula donde utiliza la notación por primera vez:

  

(...) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in 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 esto es, de hecho, un omikron capital griego. Utiliza muchos caracteres griegos y latinos, por lo que realmente no hay forma de saberlo. Dado su uso continuado de "Ordnung n log n " etc. en el texto, está claro que significa "Ordnung" (alemán para "orden" si hubiera alguna duda) en cualquier caso, pero eso Todavía podría dejar abierto el uso de una elegante griega O.

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

    
respondido por el user34528 14.09.2011 - 02:53
5

Me gusta este artículo , con la esperanza de que encuentres ¡También es útil!

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

Big O es a menudo mal utilizado. Big O o Big Oh es realmente corto para 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. Dicho algoritmo significa que existen dos constantes c1 y c2, de manera 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. 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, todos los demás factores son ignorados. 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 clasifican como el factor clave. Esto está bien, pero no tiene en cuenta temas como:

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

    
respondido por el topgun_ivard 13.09.2011 - 20:20
2

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

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

Deje que f y g sean 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 sea x > k.

Leería esto como "f (x) es big-oh de g (x)"

El big-O a veces se llama un símbolo de Landau por el matemático alemán Edmund Landau. No creo que represente nada más allá de eso. También tienes las notaciones big-Omega y big-theta similares. Los símbolos son tan arbitrarios como usar siempre theta para denotar los ángulos en tus triángulos que estaban en tu clase de Geometría Planar de la escuela secundaria.

Corrección  @ back2dos ha proporcionado una explicación satisfactoria para la O en relación con el 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 que se usó la notación, debe leer

"Analytische Zahlentheorie" por Paul Bachmann desde 1892

    
respondido por el Jonathan Henson 13.09.2011 - 20:55
1

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

En realidad, no es la letra latina Oh , es la letra griega Omicron . Desafortunadamente, esos dos tienen exactamente el mismo glifo, así 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 mnemotécnico :

  • Omicron tiene las letras M-I-C-R-O, y la semántica del símbolo de Omicron aproximadamente significa "más pequeño que"
  • Omega tiene las letras M-E-G-A, y la semántica del símbolo Omega significa aproximadamente "más grande que"
  • Theta (Θ) se parece un poco al signo de igual, y la semántica del símbolo de Theta aproximadamente significa "igual a"

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

    
respondido por el Jörg W Mittag 14.09.2011 - 03:22
-5

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 las tasas de crecimiento existentes. 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 los métodos N tiempo de ejecución (o almacenamiento) dados los elementos. Cuanto mayor sea el orden, peor será el método.
Por ejemplo, buscar un registro en una matriz es O (1) (creo que en alguna implementación de tablas hash, ese también es el caso). Agregar un valor al final de una lista de enlaces sería O (N) porque debes 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 :)

    
respondido por el SoftwareSavant 13.09.2011 - 21:46

Lea otras preguntas en las etiquetas

Comentarios Recientes

Estoy trabajando para mantener lo que denomino una variante formal de Big O, basada en la sintaxis. Puede buscarlo en Google. Las actualizaciones son esencialmente lo que sea que cambie los datos en BIG O. Big O es completamente voluntario; en general, el soporte de archivo rara vez se interfiere. BIG O nunca debe regirse por cumplir con los requisitos. Estoy investigando otras estadísticas divertidas para ello, puede que no estén en la lista actual de cajeros automáticos. <| Endoftext |> Para informar a los usuarios,... Lee mas