necesito para derivar la complejidad Big-O de esta expresión:Big-O complejidad de c^n + n * (log n)^2 + (10 * n)^c
c^n + n * (log (n))^2 + (10 * n)^c
donde c es una constante yn es una variable.
Estoy bastante seguro de que entiendo cómo derivar la complejidad de Big-O de cada término individualmente, simplemente no sé cómo cambia la complejidad de Big-O cuando los términos se combinan así.
Ideas?
Cualquier ayuda sería grande, gracias.
La O() notación considera la más alta plazo; piense en cuál dominará para valores muy, muy grandes de n.
En su caso, el término más alto es c^n, en realidad; los otros son esencialmente polinomios. Entonces, es una complejidad exponencial.
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 siguientes reglas de simplificación:
- Si f (x) es una suma de varios términos, el que tiene la mayor tasa de crecimiento se mantiene, y todo otros omitidos
- Si f (x) es un producto de varios factores, se omiten cualquier constante (términos en el producto que no dependen de x).
pensé Google es :) – akif
La respuesta depende de | c |
If | c | < = 1 es O (n * (log (n))^2)
SI | c | > 1 es O (c^n)
1 Yay una respuesta que atrapa ambos casos del valor de C. :-P –
Nunca pensé en esto antes, pero aquí va. Si la complejidad depende de la magnitud de C, ¿significa esto que también depende de las unidades utilizadas para medir C? En caso negativo, ¿en qué unidades debe medirse C? – Stewart
@Stewart No creo que c se pueda expresar en algunas unidades. Si pudiera, entonces la unidad de la expresión dependería de ny (10 * n)^c no tendría mucho sentido. –
+1 - Sí, eso es correcto. Borré mi respuesta Lo leí como n^c por alguna razón. Una –
supuesto muy importante: C tiene que ser mayor que 1. :-P –