algorithm - little - ¿Son 2 ^ n y n*2 ^ n en la misma complejidad de tiempo?
big o notation pdf (5)
Estoy de acuerdo en que n⋅2ⁿ no está en O(2ⁿ) , pero pensé que debería ser más explícito ya que el límite de uso superior no siempre se cumple.
Según la definición formal de Big-O: f(n) está en O(g(n)) si existen constantes c > 0 y n₀ ≥ 0 manera que para todo n ≥ n₀ 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á en O(f(n)) .
En otras palabras, n⋅2ⁿ tiene un límite inferior por 2ⁿ . Esto es intuitivo. Aunque ambos son exponenciales y, por lo tanto, es menos probable que se usen en la mayoría de las circunstancias prácticas, no podemos decir que son del mismo orden porque 2ⁿ necesariamente crece más lento que n⋅2ⁿ .
Los recursos que he encontrado sobre la complejidad del tiempo no están claros acerca de cuándo está bien ignorar los términos en una ecuación de complejidad de tiempo, específicamente con ejemplos no polinomiales.
Para mí es claro que, dada la forma n 2 + n + 1, los dos últimos términos son insignificantes.
Específicamente, dadas dos categorizaciones, 2 n , y n * (2 n ), ¿el segundo está en el mismo orden que el primero? ¿Importa la n multiplicación adicional allí? Por lo general, los recursos solo dicen x n es exponencial y crece mucho más rápido ... luego continúan.
Puedo entender por qué no lo haría, ya que 2 n superará en gran medida a n, pero dado que no se suman, importaría mucho al comparar las dos ecuaciones, de hecho, la diferencia entre ellas siempre será un factor de n, que parece importante por decir lo menos.
No discuto con otras respuestas que dicen que n⋅2ⁿ crece más rápido que 2ⁿ . Pero n⋅2ⁿ crece aún de forma exponencial.
Cuando hablamos de algoritmos, a menudo decimos que el tiempo que la complejidad crece es exponencial. Por lo tanto, consideramos que son 2ⁿ , 3ⁿ , 2.000001ⁿ , 2.000001ⁿ , o nuestro n⋅2ⁿ para ser el mismo grupo de complejidad con crecimientos exponenciales.
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 , que f(x) = O(c x ) .
Para n⋅2ⁿ la constante c puede ser cualquier número mayor que 2 , tomemos 3 . Entonces:
n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ y esto es menor que 1 para cualquier 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.
Tendrá que ir a la definición formal del gran O ( O ) para responder a esta pregunta.
La definición es que f(x) pertenece a O(g(x)) si y solo si el límite limsup x → ∞ (f(x)/g(x)) existe, es decir, no es infinito. En resumen, esto significa que existe una constante M , tal que el valor de f(x)/g(x) nunca es mayor que M
En el caso de su pregunta, f(n) = n ⋅ 2 n y let g(n) = 2 n . Entonces f(n)/g(n) es n que crecerá infinitamente. Por lo tanto f(n) no pertenece a O(g(n)) .
Una manera rápida de ver que n⋅2ⁿ es más grande es hacer un cambio de variable. Deje m = 2ⁿ . Entonces n⋅2ⁿ = ( log₂m )⋅m (tomando el logaritmo de base-2 en ambos lados de m = 2ⁿ da como resultado n = log₂m ), y puede demostrar fácilmente que m log₂m crece más rápido que m .
Usted preguntó "¿el segundo en el mismo orden que el primero? ¿Importa la multiplicación n adicional?" Estas son dos preguntas diferentes con dos respuestas diferentes.
n 2 ^ n crece asintóticamente más rápido que 2 ^ n. Esa es esa pregunta respondida.
Pero podría preguntarse "si el algoritmo A tarda 2 ^ n nanosegundos, y el algoritmo B toma n 2 ^ n nanosegundos, ¿cuál es el mayor n en el que puedo encontrar una solución en un segundo / minuto / hora / día / mes / año? 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 problema más grande que se puede resolver en el tiempo T es O (ln T) en ambos casos.