Big-O complejidad de c ^ n + n * (log n) ^ 2 + (10 * n) ^ c
-
25-09-2019 - |
Pregunta
necesito para derivar la complejidad de Big-O de esta expresión:
c ^ n + n * (log (n)) ^ 2 + (10 * n) ^ c
donde c es una constante y n es una variable.
Estoy bastante seguro de entender cómo derivar la complejidad de Big-O de cada término individual, sólo que no sé cómo la complejidad de Big-O cambia cuando los términos se combinan de esta manera.
Ideas?
Cualquier ayuda sería grande, gracias.
Solución
La notación O () considera la más alta plazo; Piense acerca de cuál va a dominar por mucho, valores muy grandes de n
.
En su caso, el término más alto es c^n
, en realidad; los otros son esencialmente polinomio. Por lo tanto, es la complejidad exponencial.
Otros consejos
La respuesta depende de | c |
Si | c | <= 1 es de O (n * (log (n)) ^ 2)
Si | c | > 1 el mismo de la O (c ^ n)
En el uso típico, la definición formal de notación O no se utiliza directamente; más bien, la notación O para una función f (x) se deriva por las reglas siguientes simplificaciones:
- Si f (x) es una suma de varios términos, el que tiene la mayor tasa de crecimiento se mantiene, y todos los demás omite.
- Si f (x) es un producto de varios factores, se omiten cualquier constante (términos en el producto que no dependen de x).