Técnicamente, no, no lo son. Como han comentado otros, estas son dos funciones crecientes que difieren en un factor de [matemáticas] n [/ matemáticas]. La clase [math] O (n ^ {\ log n}) [/ math] es un subconjunto apropiado de la clase [math] O (n ^ {(\ log n) +1}) [/ math] – exactamente para la misma razón por la cual [math] O (n ^ 8) [/ math] es un subconjunto apropiado de [math] O (n ^ 9) [/ math].
Sin embargo, esta no es toda la historia.
La razón principal por la cual la notación O es útil en la práctica: cuando se trata de funciones como polinomios de bajo orden, los factores constantes ya no importan. Es más claro y también más conveniente simplemente escribir “[matemáticas] O (n ^ 2) [/ matemáticas]” e ignorar los factores constantes ocultos.
- ¿Para qué se utiliza una serie de Fourier?
- Cómo entender la pregunta para poder intentar resolverla
- Estoy interesado en algoritmos. Planeo hacer una maestría en informática teórica en una de las 20 mejores universidades. ¿Cuán significativamente ayudará a hacerme digno de la industria?
- ¿Qué es mejor, una licenciatura con honores conjuntos en matemáticas / CS o matemáticas / física?
- ¿Cómo es posible este gráfico Big-theta para un algoritmo de búsqueda lineal?
En el mismo espíritu, una vez que llegamos a funciones que crecen más rápido que cualquier polinomio, los factores polinomiales dejan de importar. No hay mucha diferencia entre las funciones [matemáticas] n2 ^ n [/ matemáticas] y [matemáticas] n ^ 22 ^ n [/ matemáticas], el factor [matemáticas] 2 ^ n [/ matemáticas] es lo que importa la mayoría en ambos casos. Es por eso que tenemos otros tipos de notación además de la notación básica big-Oh. En particular, [math] \ hat {O} [/ math] y [math] \ hat {\ Theta} [/ math] son las versiones de [math] O [/ math] y [math] \ Theta [/ math ] que también “esconden” factores polinomiales. Las dos funciones mencionadas en su pregunta pertenecen a [math] \ hat {\ Theta} (n ^ {\ log n}) [/ math]. Esto captura bastante bien la sensación de que no hay mucha diferencia entre estas dos funciones.
