¿Hay variaciones de los tiempos de ejecución regulares de la notación Big-O?

9

Hay múltiples anotaciones , como u etc. Me preguntaba si hay variaciones de las que en realidad son como u , o si son matemáticamente incorrectas.OO(n)O(n2)O(2n2)O(logn2)

¿O sería correcto decir que es posible mejorar un a un ? Todavía no puedo y no necesito calcular tiempos de ejecución y no necesito mejorar nada, pero necesitaría saber si así describe sus funciones en realidad.O(5n2)O(3n2)

bv_Martn
fuente
1
No hay diferencia material entre O (5n ^ 2) y O (3n ^ 2) durante un análisis asintótico. Ambos son O (n ^ 2), y solo difieren en una constante. De hecho, en una prueba, incluso podría reducir O (5n ^ 2) a O (3n ^ 2) u O (n ^ 2) para hacer que las matemáticas sean más limpias, ya que son equivalentes. Al escribir su prueba, anota en una barra lateral que son equivalentes. De hecho, incluso puede intercambiar una O (log n) con O (n) y tener en cuenta que O (log n) <= O (n) en la barra lateral. La nota en la barra lateral le dice al lector que es intencional y no un error tipográfico. (Al menos así lo hice cuando tomé el Análisis de Algoritmo en la universidad).
jww
2
Si está utilizando la notación para deshacerse de pequeños factores, siempre puede escribir algo como "... mejora el tiempo de ejecución de 5 n 2 + o ( n 2 ) a 3 n 2 + o ( n 2 ) ", etc. O, de manera equivalente, ( 5 + o ( 1 ) ) n 2 y ( 3 + o ( 1 ) ) n 2O()5n2+o(n2)3n2+o(n2)(5+o(1))n2(3+o(1))n2. Algunos autores prefieren escribir como taquigrafía para el primero. Ver, por ejemplo, el libro de texto de Trefethen y Bau. 5n2
Yonatan N

Respuestas:

21

Me preguntaba si hay variaciones de las que existen en realidad, como O(2norte2) u O(Iniciar sesión(norte2)) , o si son matemáticamente incorrectas.

Sí, O(2norte2) u O(Iniciar sesión(norte2)) son variaciones válidas.

Sin embargo, rara vez los verá si los ve, en especial en los resultados finales. La razón es que O(2norte2) es O(norte2) . Del mismo modo, O(Iniciar sesión(norte2)) es O(Iniciar sesiónnorte) . Eso podría sorprender a los principiantes. Sin embargo, esas igualdades son más o menos la razón por la cual se introdujeron las grandes anotaciones O , para ocultar un factor constante multiplicativo que a menudo es difícil de precisar y relativamente insignificante.

¿Sería correcto decir que es posible mejorar un O(5 5norte2) a un O(3norte2) ?

No es una mejora en absoluto si la complejidad temporal de un algoritmo se cambia de O(5 5norte2) a O(3norte2) o de Ω(5 5norte2) a Ω(3norte2) , porque O(5 5norte2) es O(3norte2) mientras que Ω(5 5norte2) es Ω(3norte2) . Por lo tanto, es incorrecto decir que la complejidad temporal se ha mejorado deO(5 5norte2) aO(3n2) . Es correcto decir que la complejidad temporal de un algoritmo mejora de5n2 a3n2 , por supuesto.


Ejercicio 1. Demuestre que O(5n2)=O(3n2)=O(n2) .

Ejercicio 2. Demuestre que O(logn)=O(log(n2)) .

Ejercicio 3. Demuestre que Ω(n2+n)=Ω(n2) .

John L.
fuente
1
@bv_Martn Aquí hay un buen enlace para comprender cómo se define la notación (¡simplemente cálculo de límite simple!): math.stackexchange.com/questions/925053/…O(n)
Akshat Mahajan
2
La única vez que he visto factores constantes en la notación Big-O es cuando alguien quiere señalar que, aunque dos algoritmos son de la misma clase de complejidad, uno de ellos es estrictamente más rápido que el otro.
Mark
77
@AkshatMahajan La única respuesta a esa pregunta /math/925053 es claramente errónea. Hay muchas fuentes confiables en grandes anotaciones O
John L.
1
"Es correcto decir que la complejidad temporal de un algoritmo mejora de 5n ^ 2 a 3n ^ 2", aunque el tiempo de ejecución exacto a menudo varía para diferentes tamaños y valores de entrada. Además, esto implica ponderar todas las operaciones / enfocarse en una operación, lo que puede no decir mucho sobre los factores constantes que obtendrá en el mundo real o ser comparable a otros algoritmos que usan diferentes pesos. Entonces, si bien puede tener algunos casos de uso válidos, decir algo como lo anterior es de utilidad limitada (lo que probablemente es la razón por la que rara vez se ve).
Dukeling
1
@ Mark: Eso simplemente está mal.
user21820
13

Siempre eres libre de no usar esta notación en absoluto. Es decir, puede determinar una función f(n) mayor precisión posible y luego tratar de mejorarla. Por ejemplo, es posible que tenga un algoritmo de clasificación que haga f(n) comparaciones, por lo que podría intentar encontrar otro algoritmo de clasificación que solo haga comparaciones g(n) . Por supuesto, todo tipo de funciones f(n) existen (en teoría) y también pueden aparecer (en la práctica).

En lugar de tratar la notación Big Oh como una magia misteriosa en la que tienes que consultar a los magos para preguntar si puedes hacer algo, debes mirar su definición . Respete la definición y luego haga lo que sea necesario para hacer su trabajo.

Juho
fuente
Bueno, aún no lo necesito en la práctica. O, en teoría, en realidad, solo necesito saber si las definiciones dadas por Wikipedia O (1) -O (n!) Son las únicas que existen, o si en realidad podría describirlas de manera diferente si son diferentes, como O (7N). Mi temor es que si uso eso, un profesor de matemáticas perderá sus alas
bv_Martn
1
Cualquier definición que alguien haga existe. Debe leer con mucho cuidado lo que significa la notación u O ( n ! ) Porque su pregunta no tiene sentido. No hay atajos. Si desea comprender qué significa un contenido matemático, debe estar dispuesto a invertir algo de tiempo. O(1)O(n!)
Juho
66
@bv_Martn Es mucho más probable que el profesor de matemáticas se voltee porque está viendo una lista de ejemplos como una lista de definiciones. Gran parte del objetivo de las matemáticas es definir las cosas de una manera que las haga funcionar en general, no solo en casos específicos. Su pregunta es básicamente una versión más avanzada de "Wikipedia dice que puedo agregar uno y agregar dos y agregar diecisiete. ¿Pero también puedo agregar otros números?"
David Richerby
7

Si bien la respuesta aceptada es bastante buena, todavía no toca la razón real por la cual O(n)=O(2n) .

La notación Big-O describe escalabilidad

En esencia, la notación Big-O no es una descripción de cuánto tiempo tarda un algoritmo en ejecutarse. Tampoco es una descripción de cuántos pasos, líneas de código o comparaciones realiza un algoritmo. Es más útil cuando se usa para describir cómo un algoritmo escala con el número de entradas.

Tome una búsqueda binaria, por ejemplo. Dada una lista ordenada, ¿cómo encuentra un valor arbitrario dentro de ella? Bueno, podrías comenzar por el medio. Como la lista está ordenada, el valor medio le indicará en qué mitad de la lista se encuentra su valor objetivo. Por lo tanto, la lista que debe buscar ahora se divide por la mitad. Esto se puede aplicar de forma recursiva, luego ir al centro de la nueva lista, y así sucesivamente hasta que el tamaño de la lista sea 1 y haya encontrado su valor (o no exista en la lista). Duplicar el tamaño de la lista solo agrega un paso adicional al algoritmo, que es una relación logarítmica. Por lo tanto, este algoritmo es O(logn). El logaritmo es la base 2, pero eso no importa: el núcleo de la relación es que multiplicar la lista por un valor constante solo agrega un valor constante al tiempo.

Contraste una búsqueda estándar a través de una lista no ordenada: la única forma de buscar un valor en este caso es verificar cada uno. El peor de los casos (que es lo que Big-O implica específicamente) es que su valor está al final, lo que significa que para una lista de tamaño n , debe verificar n valores. Duplicar el tamaño de la lista duplica el número de veces que debe verificar, que es una relación lineal. O(n) . Pero incluso si tuviera que realizar dos operaciones en cada valor, algún procesamiento, por ejemplo, la relación lineal aún se mantiene. O(2n) simplemente no es útil como descriptor, ya que describiría exactamente la misma escalabilidad que O(n) .

Aprecio que muchas de estas respuestas te estén diciendo básicamente que llegues a esta conclusión tú mismo leyendo la definición de Big-O. Pero esta comprensión intuitiva me llevó bastante tiempo comprender y, por lo tanto, te lo explico lo más claramente posible.

dispersión
fuente
55
El mayor problema con este tipo de respuesta es que no toca la definición de Big Oh, sino que solo la usa como una especie de magia intuitiva como en "ver cuando haces esto y esto, es ". Personalmente, creo que es mucho más instructivo decirle a alguien que Big Oh no tiene absolutamente nada que ver con algoritmos necesariamente y comenzar con eso. O(n)
Juho
3
@Juho Instructivo, tal vez, pero en última instancia inútil para la gran mayoría de los informáticos.
dispersión
44
Con esto debo estar en desacuerdo. Etiquetar a uno mismo como informático no debería ser una excusa para no entender lo que significa una notación que uno usa, es decir, omitir todas las matemáticas.
Juho
3
Si. No tengo ninguna objeción a que los programadores no entiendan estas cosas, pero si quieres llamarte a ti mismo un científico de la computación , entonces este es el material principal.
David Richerby
2
@dkaeae No, me refiero a las personas que trabajan en otras carreras en el campo, como los desarrolladores de software.
dispersión
5

Puedes escribir O(F)para cualquier funciónFY eso tiene un sentido perfecto. Según la definición,g(n)=O(f(n)) if there is some constant c such that g(n)cf(n) for all large enough n. Nothing in that definition says that f must be some sort of "nice" function.

But, as other answers have pointed out, g(n)=O(f(n)) and g(n)=O(2f(n)) describe exactly the same situation: if g(n)cf(n) for all all large enough n, then we also have g(n)c22f(n), so g(n)=O(2f(n)), also (taking the constant to be c/2).

As a side issue, don't write "logn2", because it's not 100% clear what it means. You could say that it obviously means log(n2) but almost everybody would write that as 2logn, so it puts doubt in the reader's mind.

Also, note that big-O notation has nothing to do with runtimes per se. It's just a notation for relationships between functions. Those functions are often used to measure the runtimes of algorithms but that's just one application, just like measuring people's heights is just one application of numbers.

David Richerby
fuente
4

Look at the definition of O(f(n)), and you see that for example O(2n^2) and O(n^2) are exactly the same. Changing an algorithm from 5n^2 to 3n^2 operations is a 40 percent improvement. Changing from O(5n^2) to O(3n^2) isn’t actually any change, they are the same.

Again, read the definition of O(f(n)).

gnasher729
fuente
4

It may be helpful to understand that Big-O describes a set of functions. That is O(f(n))={g(n)|n,c>0:m>n:c×g(m)f(m)}

The usage of = is kind of unfortunate and using would make that relationship a lot clearer. but the set notation symbols are a bit difficult to type so now we are stuck with the current convention.

This then shows that O(n)=O(2n) Or that constant factors don't matter when defining the Big O.

ratchet freak
fuente
4
The equality convention isn't really about typing. It's because the usefulness of expressions such as log(n!)=nlognn+O(logn) encourages us to view O(f) as both "the set of functions such that [...]" and "some function such that [...]"
David Richerby