En matemáticas, una función polilogarítmica en es un polinomio formado a partir del logaritmo de , es decir:
La notación se utiliza a menudo como forma concisa para , análoga a para .
En ciencias de la computación, las funciones polilogarítmicas se dan como orden de magnitud del tiempo de cálculo necesario para algunas operaciones de estructura de datos. Además, la función exponencial de una función polilogarítmica produce una función con crecimiento casi polinómico, y se dice que los algoritmos con esta complejidad temporal requieren tiempo casi polinómico.
Todas las funciones polilogarítmicas de son para cada exponente (para el significado de este símbolo, consúltese cota superior asintótica), es decir, una función polilogarítmica crece más lentamente que cualquier exponente positivo. Esta observación es la base de la notación O débil .
Referencias
Categoría:Análisis matemático Categoría:Polinomios Categoría:Análisis de algoritmos