algorithm - resueltos - ¿Por qué ignoramos los coeficientes en la notación Big O?

notacion big o ejercicios resueltos

Question

Al buscar respuestas relacionadas con la notación "O grande", he visto muchas respuestas de SO como this , this o this , pero aún no he entendido claramente algunos puntos.

¿Por qué ignoramos los coeficientes?

Por ejemplo, this dice que la complejidad final de 2N + 2 es O(N) ; eliminamos el coeficiente 2 y la constante final 2 también.

Eliminar la constante final de 2 tal vez comprensible. Después de todo, N puede ser muy grande y, por lo tanto, "olvidar" los 2 finales solo puede cambiar el total general en un pequeño porcentaje.

Sin embargo, no puedo entender claramente cómo eliminar el coeficiente principal no hace la diferencia. Si los 2 anteriores se convirtieran en 1 o 3 , el cambio porcentual en el total general sería grande.

De manera similar, aparentemente 2N^3 + 99N^2 + 500 es O(N^3) . ¿Cómo ignoramos el 99N^2 junto con el 500 ?

Answer 1

Otra cosa es que, lo que he entendido, la complejidad de 2N ^ 3 + 99N ^ 2 + 500 será O (N ^ 3). Entonces, ¿cómo ignoramos / eliminamos la porción 99N ^ 2 incluso? ¿No hará la diferencia cuando digamos que N es una milion?

Así es, en ese caso, el término 99N ^ 2 está muy opacado por el término 2N ^ 3. El punto donde se cruzan está en N = 49.5, mucho menos que un millón.

Pero usted menciona un buen punto. De hecho, el análisis de complejidad computacional asintótica a menudo se critica por ignorar factores constantes que pueden hacer una gran diferencia en las aplicaciones del mundo real. Sin embargo, big-O sigue siendo una herramienta útil para capturar la eficiencia de un algoritmo en unas pocas sílabas. A menudo es el caso de que un algoritmo n^2 sea ​​más rápido en la vida real que un algoritmo n^3 para n no trivial, y casi siempre es el caso de que un algoritmo log(n) sea ​​mucho más rápido que un algoritmo n^2 .

Además de ser un criterio práctico para aproximar la eficiencia práctica, también es una herramienta importante para el análisis teórico de la complejidad del algoritmo. Muchas propiedades útiles surgen de la capacidad de composición de los polinomios; esto tiene sentido porque el bucle anidado es fundamental para el cálculo, y esas corresponden a números de pasos polinomiales. Usando el análisis de complejidad asintótica, puede probar un conjunto rico de relaciones entre diferentes categorías de algoritmos, y eso nos enseña cosas acerca de qué tan exactamente pueden resolverse ciertos problemas.

Answer 2

La razón matemática:

La razón real por la que hacemos esto es la forma en que se define la O-Notación grande: una serie (o permite usar la función de palabra) f (n) está en O (g (n)) cuando la serie f (n) / g (n) está acotada. Ejemplo:

f (n) = 2 * n ^ 2
g (n) = n ^ 2

f (n) está en O (g (n)) porque (2 * n ^ 2) / (n ^ 2) = 2 cuando n se acerca al Infinito. El término (2 * n ^ 2) / (n ^ 2) no se vuelve infinitamente grande (siempre es 2), por lo que el cociente está limitado y, por lo tanto, 2 * n ^ 2 está en O (n ^ 2).

Otro:

f (n) = n ^ 2
g (n) = n

El término n ^ 2 / n (= n) se vuelve infinitamente grande, ya que n va al infinito, por lo que n ^ 2 no está en O (n).

El mismo principio se aplica, cuando tienes

f (n) = n ^ 2 + 2 * n + 20
g (n) = n ^ 2

(n ^ 2 + 2 * n + 20) / (n ^ 2) también está acotada, porque tiende a 1, cuando n va al infinito.

La notación Big-O básicamente describe que su función f (n) es (desde algún valor de n hasta infinito) más pequeña que una función g (n), multiplicada por una constante. Con el ejemplo anterior:

2 * n ^ 2 está en O (n ^ 2), porque podemos encontrar un valor C, de modo que 2 * n ^ 2 es más pequeño que C * n ^ 2. En este ejemplo, podemos elegir que C sea 5 o 10, por ejemplo, y la condición se cumplirá.

Entonces, ¿qué sacas de esto? Si sabe que su algoritmo tiene una complejidad de O (10 ^ n) e ingresa una lista de 4 números, puede tomar solo un corto tiempo. ¡Si ingresas 10 números, tomará un millón de veces más! Si es un millón de veces más o 5 millones de veces más, realmente no importa aquí. Siempre puede usar 5 computadoras más para él y hacer que funcione en la misma cantidad de tiempo, el verdadero problema aquí es que se escala increíblemente mal con el tamaño de entrada.

Answer 3

Big O proporciona una buena estimación de qué algoritmos son más eficientes para entradas más grandes, en igualdad de condiciones; esta es la razón por la que para un algoritmo con un factor n ^ 3 y n ^ 2 ignoramos el factor n ^ 2, porque incluso si el factor n ^ 2 tiene una gran constante, eventualmente estará dominado por el factor n ^ 3.

Sin embargo, los algoritmos reales incorporan más que un simple análisis de Big O, por ejemplo, un algoritmo de clasificación a menudo comenzará con un algoritmo de partición O (n * log (n)) como quicksort o mergesort, y cuando las particiones se vuelvan lo suficientemente pequeñas, el algoritmo cambiará a un algoritmo O (n ^ 2) más simple como inserción, por ejemplo, para entradas pequeñas, la inserción es generalmente más rápido, aunque un análisis Big O básico no revela esto.

Los factores constantes a menudo no son muy interesantes y, por lo tanto, se omiten. Ciertamente, una diferencia en los factores del orden de 1000 es interesante, pero generalmente la diferencia en los factores es menor, y luego hay muchos más factores constantes para considerar que Puede dominar las constantes de los algoritmos. Digamos que tengo dos algoritmos, el primero con el tiempo de ejecución 3 * n y el segundo con el tiempo de ejecución 2 * n, cada uno con una complejidad de espacio comparable. Este análisis asume un acceso uniforme a la memoria; ¿Qué pasa si el primer algoritmo interactúa mejor con el caché, y esto compensa el peor factor constante? ¿Qué sucede si se le pueden aplicar más optimizaciones del compilador, o se comporta mejor con el subsistema de administración de memoria, o requiere IO menos costoso (por ejemplo, menos búsquedas de disco o menos combinaciones de bases de datos, etc.) y así sucesivamente? El factor constante para el algoritmo es relevante, pero hay muchas más constantes que deben considerarse. A menudo, la forma más sencilla de determinar cuál es el mejor algoritmo es simplemente ejecutándolos en algunas entradas de muestra y cronometrando los resultados; Depender excesivamente de los factores constantes de los algoritmos ocultaría este paso.

Answer 4

Desde el punto de vista de la teoría (complejidad), los coeficientes representan detalles de hardware que podemos ignorar. Específicamente, el teorema de aceleración lineal determina que para cualquier problema siempre podemos lanzar una cantidad de hardware (dinero) exponencialmente creciente en una computadora para obtener un aumento lineal en la velocidad.

Por lo tanto, el módulo de hardware caro compra dos algoritmos que resuelven el mismo problema, uno al doble de la velocidad del otro para todos los tamaños de entrada, se consideran esencialmente iguales.

La notación Big-O (Landau) tiene sus orígenes independientemente en la teoría de números, donde uno de sus usos es crear una especie de equivalencia entre funciones: si una función dada está delimitada por otra y simultáneamente está delimitada por una versión escalada de esa La misma otra función, entonces las dos funciones son esencialmente las mismas desde un punto de vista asintótico. La definición de Big-O (en realidad, "Big-Theta") captura esta situación: el "Big-O" (Theta) de las dos funciones es exactamente igual.

El hecho de que la notación Big-O nos permita ignorar la constante líder al comparar el crecimiento de funciones hace de Big-O un vehículo ideal para medir varias calidades de algoritmos mientras respeta (ignora) las optimizaciones "gratuitas" ofrecidas por el teorema de aceleración lineal.

Answer 5

El propósito de la notación Big-O es encontrar cuál es el factor dominante en el comportamiento asintótico de una función, ya que el valor tiende hacia el infinito.

A medida que recorremos el dominio de la función, algunos factores se vuelven más importantes que otros.

Imagina f(n) = n^3+n^2 . Cuando n va al infinito, n^2 vuelve cada vez menos relevante cuando se compara con n^3 .

Pero eso es solo la intuición detrás de la definición. En la práctica, ignoramos algunas partes de la función debido a la definición formal:

f(x) = O(g(x)) como x->infinity

si y solo si hay una M real positiva y una x_0 real como

|f(x)| <= M|g(x)| para todas las x > x_0 .

Eso está en wikipedia . Lo que realmente significa es que hay un punto (después de x_0 ) después del cual un múltiplo de g(x) domina f(x) . Esa definición actúa como un límite superior suelto en el valor de f(x) .

De eso podemos derivar muchas otras propiedades, como f(x)+K = O(f(x)) , f(x^n+x^n-1)=O(x^n) , etc. Es solo una cuestión de usar la definición para probarlos.

En especial , la intuición detrás de la eliminación del coeficiente ( K*f(x) = O(f(x)) ) reside en lo que intentamos medir con la complejidad computacional. En última instancia, todo se trata de tiempo (o cualquier recurso, en realidad). Pero es difícil saber cuánto tiempo toma cada operación. Un algoritmo puede realizar operaciones 2n y el otro n , pero este último puede tener asociado un gran tiempo constante. Entonces, para este propósito, no es fácil razonar acerca de la diferencia entre n y 2n .

Answer 6

La notación Big O no es una medida absoluta de complejidad.

Más bien es una designación de cómo la complejidad cambiará a medida que cambia la variable. En otras palabras, a medida que N aumenta, la complejidad aumentará Big O (f (N)).

Para explicar por qué no se incluyen los términos, observamos qué tan rápido aumentan los términos.

Por lo tanto, Big O (2n + 2) tiene dos términos 2n y 2. Al observar la tasa de aumento de Big O (2), este término nunca aumentará, no contribuye a la tasa de aumento, por lo que desaparece. Además, como 2n aumenta más rápido que 2, el 2 se convierte en ruido cuando n se vuelve muy grande.

De manera similar, Big O (2n ^ 3 + 99n ^ 2) compara Big O (2n ^ 3) y Big O (99n ^ 2). Para valores pequeños, digamos n <50, el 99n ^ 2 contribuirá con un porcentaje nominal mayor que 2n ^ 3. Sin embargo, si n se vuelve muy grande, digamos 1000000, entonces 99n ^ 2 aunque nominalmente grande es insignificante (cerca de 1 millón) en comparación con el tamaño de 2n ^ 3.

Como consecuencia, Big O (n ^ i) <Big O (n ^ (i + 1)).

Los coeficientes se eliminan debido a la definición matemática de Big O.

Para simplificar la definición, dice Big O (f (n)) = Big O (f (cn)) para una constante c. Esto debe tomarse por fe porque la razón de esto es puramente matemática, y como tal, la prueba sería demasiado compleja y seca para explicarla en términos simples.

Answer 7

Para aplicaciones prácticas, las constantes son importantes, por lo que O(2 n^3) será mejor que O(1000 n^2) para las entradas con n menor que 500 .

Hay dos ideas principales aquí: 1) Si su algoritmo debería ser excelente para cualquier entrada, debería tener una complejidad de tiempo baja, y 2) que n^3 crezca mucho más rápido que n^2 , que perfering n^3 sobre n^2 casi nunca tiene sentido.