¿Cuál de las opciones dadas proporciona el orden creciente de complejidad asintótica de las funciones f1, f2, f3 y f4?
f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn)
(A) f3, f2, f4, f1
(B) f3, f2, f1, f4
(C) f2, f3, f1, f4
(D) f2, f3, f4, f1
Respuesta: (A)
Explicación:
f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn)
Excepto f3, todos los demás son exponenciales. Entonces f3 es definitivamente el primero en la salida. Entre los restantes, n^(3/2) es el siguiente.
Una forma de comparar f1 y f4 es tomar el registro de ambas funciones. El orden de crecimiento de Log(f1(n)) es Θ(n) y el orden de crecimiento de Log(f4(n)) es Θ(Logn * Logn). Dado que Θ(n) tiene un mayor crecimiento que Θ(Logn * Logn), f1(n) crece más rápido que f4(n).
La siguiente es otra forma de comparar f1 y f4.
Comparemos f4 y f1. Tomemos algunos valores para comparar
n = 32, f1 = 2^32, f4 = 32^5 = 2^25 n = 64, f1 = 2^64, f4 = 64^6 = 2^36 ............... ...............
Consulte también http://www.wolframalpha.com/input/?i=2^n+vs+n^%28log+n%29
Gracias a fella26 por sugerir la explicación anterior.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA