En informática, ¿por qué cuando un algoritmo tiene un tiempo de ejecución de O (2 ^ n), donde n es un número natural, no se considera polinomial?

Answer 1

Un algoritmo con complejidad de tiempo [matemática] t (n) [/ matemática] tiene complejidad de tiempo polinomial si [matemática] t (n) = O (n ^ k) [/ matemática] para alguna constante entera [matemática] k [/ matemáticas]. En otras palabras, por la definición de notación asintótica, tenemos que existe una constante positiva de valor real [matemática] c [/ matemática] y un límite [matemática] n_0 [/ matemática] tal que [matemática] t (n) \ leq c \ cdot n ^ k [/ math] siempre que [math] n \ geq n_0 [/ math].

Sin embargo, no hay [matemática] c [/ matemática] y no [matemática] n_0 [/ matemática] tal que la función [matemática] t (n) = 2 ^ k [/ matemática] satisfaga esto para cualquier [matemática] k [/matemáticas]. Supongamos que tenemos una [matemática] c [/ matemática] y [matemática] n_0 [/ matemática] tal que

[matemáticas] 2 ^ n \ leq c \ cdot n ^ k [/ matemáticas]

para algunos [matemática] k. [/ matemática] Pero entonces, dado que las funciones logarítmicas son monótonas, tendríamos

[matemáticas] \ log_2 (2 ^ n) = n \ leq \ log_2 (c \ cdot n ^ k) = \ log_2 c + k \ log_2 n [/ math]

entonces

[matemáticas] n \ leq \ log_2 c + k \ log_2 n [/ matemáticas]

Esto claramente no puede sostenerse, ya que [math] n> \ log_2 n [/ math] por cada [math] n \ geq 1 [/ math] (tome cualquier [math] n> (k + 1) \ log_2 c [/ math ] donde [matemáticas] n> c [/ matemáticas] para ver esto).

Answer 2

Si [math] n [/ math] fuera un número natural, [math] O (2 ^ n) [/ math] sería polinomial. Por ejemplo, si [matemática] n = 3 [/ matemática], entonces [matemática] O (2 ^ n) = O (8) = O (1) [/ matemática], que ciertamente es un polinomio. Sin embargo, [matemáticas] n [/ matemáticas] no es un número natural. [matemáticas] n [/ matemáticas] es una variable que puede tomar valores naturales. Cuando [math] n [/ math] se usa de esta manera, los polinomios se ven como [math] n ^ 3 + 8n ^ 2 + 5n + 4 [/ math], no como [math] 2 ^ n [/ math]. En un polinomio, los valores fijos van en los exponentes y las variables como [math] n [/ math] están limitadas a la base de los exponentes.

Answer 3

La función [matemáticas] f (n) = 2 ^ n [/ matemáticas] crece más rápido que cualquier polinomio. Un polinomio crece a la velocidad de [matemática] g (n) = n ^ C [/ matemática] para alguna constante C (el coeficiente principal). Pero es fácil verificar que [math] \ lim_ {n \ rightarrow \ infty} \ frac {2 ^ n} {n ^ C} = \ infty [/ math], entonces [math] 2 ^ n [/ math] no puede estar limitado por ningún tiempo constante [matemática] n ^ C [/ matemática], independientemente de cuán grande sea esa constante [matemática] C [/ matemática].

Answer 4

Porque el grado del polinomio está cambiando en función del tamaño de la entrada. El tiempo polinomial no es solo algo que puedes escribir como un polinomio. Significa que la complejidad del problema se escala con la entrada en un tiempo polinómico. En términos prácticos, 2 ^ n es una escala extremadamente pobre. Incluso un pokinominal alto como 2 ^ 1000 es más fácil de hacer cuando n es 100 o más, y 100 tiende a ser bastante pequeño para la mayoría de los problemas prácticos. No hay una expresión polinominal que siempre será más grande que ella. A menudo ves expresiones como 2 * lg (n) que se consideran polinominales, porque siempre son más rápidas que n ^ 2.

Answer 5

Porque 2 ^ n aumenta más rápido que cualquier función polinómica de n para n lo suficientemente grande.

Puede tener f (n) = 273 * n ^ (1000) + 12n + 7, que es un polinomio de orden 1000, pero para n lo suficientemente grande, 2 ^ n siempre será mayor.

Las funciones exponenciales aumentan más rápido que cualquier función polinómica posible para n grande, por lo que tienen una O grande diferente.