Función polilogarítmica

En matemáticas, una función polilogarítmica en Plantilla:Mvar es un polinomio formado a partir del logaritmo de Plantilla:Mvar, es decir:

$a_k(\log n{)}^k+a_{k-1}(\log n{)}^{k-1}+\cdots +a_1(\log n)+a_0.$

La notación Plantilla:Math se utiliza a menudo como forma concisa para Plantilla:Math, análoga a Plantilla:Math para Plantilla:Math.

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 Plantilla:Mvar son Plantilla:Math para cada exponente Plantilla:Math (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 Plantilla:Math.