Solución:
A continuación se muestran algunas funciones comunes de Big-O al analizar algoritmos.
- O (1) – tiempo constante
- O (registro (n)) – tiempo logarítmico
- O ((registro (n))C) – tiempo polilogarítmico
- O (norte) – tiempo lineal
- O (norte2) – tiempo cuadrático
- O (norteC) – tiempo polinomial
- O (Cnorte) – tiempo exponencial
- O (¡norte!) – tiempo factorial
(n = tamaño de la entrada, c = alguna constante)
Aquí está el gráfico modelo que representa la complejidad Big-O de algunas funciones
salud 🙂
créditos gráficos http://bigocheatsheet.com/
Mira esto.
Exponencial es peor que polinomio.
O (n ^ 2) cae en la categoría cuadrática, que es un tipo de polinomio (el caso especial del exponente es igual a 2) y mejor que exponencial.
Exponencial es mucho peor que el polinomio. Mira como crecen las funciones
n = 10 | 100 | 1000
n^2 = 100 | 10000 | 1000000
k^n = k^10 | k^100 | k^1000
k ^ 1000 es excepcionalmente grande a menos que k sea más pequeño que algo como 1.1. Por ejemplo, algo así como cada partícula del universo tendría que hacer 100 mil millones de billones de billones de operaciones por segundo durante billones de billones de billones de años para lograrlo.
No lo calculé, pero ES ASÍ DE GRANDE.
O (n ^ 2) es el tiempo polinomial. El polinomio es f (n) = n ^ 2. Por otro lado, O (2 ^ n) es el tiempo exponencial, donde la función exponencial implícita es f (n) = 2 ^ n. La diferencia es si la función de n coloca a n en la base de una exponenciación o en el exponente mismo.
Cualquier función de crecimiento exponencial crecerá significativamente más rápido (a largo plazo) que cualquier función polinomial, por lo que la distinción es relevante para la eficiencia de un algoritmo, especialmente para valores grandes de n.