Notación O grande de una expresión

Question

Si tengo un algoritmo que requiere 4n^2 + 7n movimientos para lograrlo, ¿cuál es su O?O(4n^2)?¿O(n^2)?

Sé que 7n está cortado, pero no sé si debo mantener el coeficiente n^2 o no.

Gracias

Answer 1

Usted debe dejar caer coeficientes porque la pregunta está pidiendo realmente "en el orden de", que trata de caracterizarla como lineal, exponencial, logarítmica, etc ... Es decir, cuando n es muy grande, el coeficiente es de poca importancia.

Esto también explica por qué se le cae el + 7n, porque cuando n es muy grande, ese término tiene relativamente poca importancia a la respuesta final. Si está familiarizado con el cálculo, se podría decir lim n-> inf (4 * n ^ 2 + 7n) ~ = lim n-> inf (4 * n ^ 2) = lim ~ n-> inf (n ^ 2)

También se puede pensar acerca de esto en un sentido gráfica ... es decir, si se hace un gráfico de la función 4n + 2 ^ 7n para valores más grandes de n, un matemático podría decir "parece que n ^ 2". Por supuesto, tendría que ser un matemático bastante liberal, ya que esto no es una declaración rigurosa, pero eso es básicamente lo que O (...) está tratando de transmitir.

Answer 2

Los coeficientes no son relevantes en Big O notación, lo que es sólo O (n ² ). Como Wikipedia explica :

  

[...] los coeficientes se vuelven irrelevantes si comparamos a cualquier otra orden de expresión, tales como una expresión que contiene un término n ³ o n ² .

Answer 3

Cualquiera que lea o escriba sobre la complejidad de los algoritmos debería saber exactamente cuál es el Símbolos Landau y notaciones asintóticas de lo contrario no entienden realmente lo que está pasando o simplemente tienen una idea aproximada (y a menudo engañosa).

Para simplificar (mucho), dejemos f y g ser dos funciones f : N -> N y g : N -> N.Nosotros decimos eso f is O(g) si y solo si hay una constante M > 0 tal que |f(n)| < M|g(n)|, para todos n > M.Es decir, de manera más informal, partiendo de un gran valor de n, todos los valores f(n) son menores que un múltiplo de g(n) (es decir, g crece más rápido que f).

Esa definición equivale a

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

Entonces, tomemos f(n) = 4n^2 + 7n y g(n) = n^2, y tratar de demostrar f is O(g) (voy a omitir {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

Esto implica que hay una M tal que n > M ==> |f(n)| < M|g(n)|, y por lo tanto f is O(g).

Así que técnicamente es correcto decir 4n^2 + 7n is O(4n^2), como es correcto decir 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), etcétera.Pero para que tenga sentido, nos interesa el límite inferior.Así que si f is O(e^n) y f is O(n^2), estamos más interesados ​​en saber que f is O(n^2), ya que esto es mucho más restrictivo.

nota MUY IMPORTANTE

Lo que es extremadamente importante al elegir un algoritmo es entender que notaciones con O grande se refiere a casos asintóticos, es decir, cuando se considera Insumos enormes, extremadamente inimaginables., que puede ir mucho más allá del poder computacional disponible en el universo conocido (es decir, conjuntos de entradas infinitos, expresados ​​matemáticamente por {n -> +oo}).

Para usos prácticos (es decir, no entonces entradas enormes), al elegir un algoritmo, seguramente observará los algoritmos candidatos notaciones con O grande, pero debe asegurarse de que el algoritmo elegido esté bien adaptado (y funcione mejor) para su entrada (esperada).

Por último, los algoritmos que funcionan con mejor rendimiento suelen ser más difíciles de entender e implementar correctamente.También debes considerar este hecho al elegir un algoritmo (es decir, es el tiempo que pasaré depurando y arreglando mi implementación de este algoritmo considerablemente superior al tiempo que tendría que esperar con otro algoritmo, con una notación de O grande peor?.Si es así, debería considerar el algoritmo más simple y menos eficiente, ya que la solución general sería más eficiente).

Answer 4

Es O (n ^ 2). factores constantes "se mueven en la O". Sólo se mantenga el mayor exponente ya que este es el dominante. Y se puede dejar de lado los coeficientes ya que cuando se comparan diferentes algoritmos incluso muy grandes coeficientes resultan en números totales más pequeños que tener un exponente más grande (con n suficientemente grande).

Answer 5

Una declaración como

4n² + 7n = O(n²)

significa que por alguna c multiplicador constante, la expresión cn² finalmente superará 4n² + 7n. No es técnicamente incorrecto dejar el coeficiente de no - O(n²) y O(4n²) significan exactamente lo mismo, porque cualquier c constante para la ex puede ser reemplazado por c/4 para el segundo. Sin embargo, tal cosa no está tan clara, posiblemente engañosa, y definitivamente no estándar.

Answer 6

Matemáticamente hablando, podría escribir O (4n²). Esto significa que la función de la complejidad de los algoritmos se comporta como n-> 4n² hacia el infinito positivo.

Sin embargo, en ciencias de la computación / algoritmo, sólo se escribe O (N ²), que es suficiente para clasificar su algoritmo.