¿Son 2 ^ n y n * 2 ^ n en la misma complejidad de tiempo?

178

Los recursos que he encontrado sobre la complejidad del tiempo no tienen claro cuándo está bien ignorar los términos en una ecuación de complejidad del tiempo, específicamente con ejemplos no polinómicos.

Para mí está claro que dada algo de la forma n 2 + n + 1, los dos últimos términos son insignificantes.

Específicamente, dadas dos categorizaciones, 2 n y n * (2 n ), ¿la segunda está en el mismo orden que la primera? ¿Importa la n multiplicación adicional allí? Por lo general, los recursos solo dicen que x n es exponencial y crece mucho más rápido ... luego continúe.

Puedo entender por qué no lo haría, ya que 2 n superará en gran medida a n, pero debido a que no se suman, sería muy importante al comparar las dos ecuaciones, de hecho, la diferencia entre ellas siempre será un factor de n, lo que parece importante por decir lo menos.

algorithm big-o complexity-theory time-complexity matty-d
fuente
8
En mi opinión, dado que NLogN se considera estrictamente más lento que N, pero a la mayoría de la gente no le importa cuánto, es seguro decir que N2 ^ N es simplemente más lento que 2 ^ N, pero no "lo suficientemente lento" para las personas preocuparse ..
Jack
@tobias_k, entiendo este punto, pero considere el ejemplo de O (n!). ¿Sería realmente diferente un término n? O (n!) Es a O (n * n!) Como O (n!) Es a O ((n + 1)!) También conocido como el mismo gráfico simplemente desplazado. Sin embargo, el crecimiento es el mismo ... En este caso, aunque uno sea estrictamente grande, ¿el crecimiento es diferente? ¿No es esto lo que le importa a la complejidad del tiempo?
matty-d
3
@JackWu, pero a la mayoría de la gente no le importa cuánto hasta que tenga que ordenar cientos de millones de registros con nlogn en lugar de n :)
CB
44
De hecho, n! = o((n+1)!)es decir, crece estrictamente más lentamente asintóticamente.
chepner
16
Tenga en cuenta que esto no tiene nada que ver con la teoría de la complejidad, es "solo" acerca de los aymptóticos. Además, este tipo de preguntas probablemente sea mejor en Informática .
Raphael

Respuestas:

231

Tendrá que ir a la definición formal de la gran O ( O) para responder esta pregunta.

La definición es que f(x)pertenece a O(g(x))si y solo si el límite existe, es decir, no es infinito. En resumen, esto significa que existe una constante , de modo que el valor de nunca es mayor que .limsupx → ∞ (f(x)/g(x))Mf(x)/g(x)M

En el caso de su pregunta let and let . Entonces es lo que seguirá creciendo infinitamente. Por lo tanto , no pertenece a .f(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n))

Ivaylo Strandjev
fuente
55
Para una definición un poco más fácil de leer, vea aquí
Alden
3
Hablando formalmente, no puedes tomar el límite de O(f(x)/g(x)); La notificación big-O es una forma abreviada de un conjunto de funciones, no una sola función cuyo valor puede limitar. Sin embargo, creo que es cierto que puedes demostrarlo f(x) = O(g(x))si lim(x->infinity) f(x)/g(x)existe.
chepner
44
El límite no tiene que existir; la relación solo tiene que estar limitada por una constante para x suficientemente grande. Por ejemplo, 2 + sin (x) está en O (1), pero (2 + sin (x)) / 1 no se acerca a un límite como x-> infinito.
user2357112 es compatible con Monica
2
La definición sería correcta con en lim suplugar de lim.
David Eisenstat
11
@IvayloStrandjev, tenga en cuenta que su descripción breve es incorrecta. Esto debe ser cierto para un valor suficientemente grande x, no para todos los valores de x.
K.Steff
85

Una forma rápida de ver que n⋅2ⁿes más grande es hacer un cambio de variable. Dejar m = 2ⁿ. Luego n⋅2ⁿ = ( log₂m )⋅m(tomando el logaritmo de base 2 en ambos lados de los m = 2ⁿdados n = log₂m), y puede mostrar fácilmente que m log₂mcrece más rápido que m.

chepner
fuente
3
¡Gracias! Esta es la mejor respuesta en mi opinión. Las pruebas basadas en definiciones formales son correctas, pero si tiene algún obstáculo que superar, una analogía muy cómoda y familiar hará el trabajo mejor y más rápido.
John P
1
Estúpida pregunta, ¿qué es lg? ¿Logaritmo en base 2?
Pierre Arlaud
3
Es una abreviatura perezosa. En ciencias de la computación, tiende a significar la base 2 porque se debe principalmente a estrategias de divide y vencerás. En notación big-O, podría representar cualquier cosa, porque el logaritmo base-x de un número difiere de su logaritmo base-y solo por un factor constante, independientemente de x e y.
chepner
3
En retrospectiva, debo señalar que lges la notación ISO para un logaritmo de base 10, en lugar del uso agnóstico de base más comúnmente utilizado cuando se discuten los tiempos de ejecución asintóticos. Ver en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
Bien, claro, pero no entiendo por qué es más obvio que m log m crece más rápido que m, que n 2 ^ n crece más rápido que 2 ^ n.
djechlin
10

Estoy de acuerdo en que n⋅2ⁿno está O(2ⁿ), pero pensé que debería ser más explícito ya que el límite de uso superior no siempre se cumple.

Por la definición formal de Big-O: f(n)está en O(g(n))si existen constantes c > 0y n₀ ≥ 0tal que para todo lo n ≥ n₀que tenemos f(n) ≤ c⋅g(n). Se puede demostrar fácilmente que no existen tales constantes para f(n) = n⋅2ⁿy g(n) = 2ⁿ. Sin embargo, se puede demostrar que g(n)está adentro O(f(n)).

En otras palabras, n⋅2ⁿes menor delimitado por 2ⁿ. Esto es intuitivo. Aunque ambos son exponenciales y, por lo tanto, es poco probable que se usen en la mayoría de las circunstancias prácticas, no podemos decir que sean del mismo orden porque 2ⁿnecesariamente crecen más lentamente que n⋅2ⁿ.

zpr
fuente
f(n) = 2*2^nCreo que quisiste decir n*2^n?
tobias_k
4

No discuto con otras respuestas que dicen que n⋅2ⁿcrece más rápido que 2ⁿ. Pero n⋅2ⁿcrece todavía es solo exponencial.

Cuando hablamos de algoritmos, a menudo decimos que la complejidad del tiempo crece es exponencial. Por lo tanto, consideramos que 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, o de nuestro n⋅2ⁿser mismo grupo de complejidad exponencial con crece.

Para darle un poco de sentido matemático, consideramos que una función f(x)crece (no más rápido que) exponencialmente si existe tal constante c > 1, eso .f(x) = O(cx)

Para n⋅2ⁿla constante cpuede ser cualquier número mayor que 2, tomemos 3. Luego:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿy esto es menos que 1para cualquiera n.

Entonces 2ⁿcrece más lento que n⋅2ⁿ, el último a su vez crece más lento que 2.000001ⁿ. Pero los tres crecen exponencialmente.

Andrey
fuente
En el último ejemplo, n * 2 ^ n es mayor que 2.000001 ^ n hasta n = 34,726,000. En ese punto 2 ^ n es un número con más de 10 millones de dígitos, por lo que realmente no importa ...
gnasher729
1
@ gnasher729 Es solo una constante que podemos omitir ya que f (n) y c * f (n) es la misma complejidad en términos de big-O. por ejemplo, 40'000'000 * 2.000001 ^ n es mayor que n * 2 ^ n de inmediato. Pero tiene razón, en realidad no importa, yo diría que realmente no importa una vez que alcancemos el crecimiento exponencial (a menos que obtengamos solo pequeños valores de n).
Andrey
2

Usted preguntó "¿el segundo está en el mismo orden que el primero? ¿Importa la n multiplicación adicional allí?" Estas son dos preguntas diferentes con dos respuestas diferentes.

n 2 ^ n crece asintóticamente más rápido que 2 ^ n. Esa es la pregunta contestada.

Pero podría preguntar "si el algoritmo A toma 2 ^ n nanosegundos, y el algoritmo B toma n 2 ^ n nanosegundos, ¿cuál es el n más grande donde puedo encontrar una solución en un segundo / minuto / hora / día / mes / año? Y las respuestas son n = 29/35/41/46/51/54 vs. 25/30/36/40/45/49. No hay mucha diferencia en la práctica.

El tamaño del mayor problema que se puede resolver en el tiempo T es O (ln T) en ambos casos.

gnasher729
fuente