En matemáticas , una función polilogarítmica en n es un polinomio en el logaritmo de n , [1]
La notación log k n se utiliza a menudo como abreviatura de (log n ) k , análoga a sin 2 θ para (sin θ ) 2 .
En informática , las funciones polilogarítmicas ocurren como el orden del tiempo para algunas operaciones de estructuras de datos . Además, la función exponencial de una función polilogarítmica produce una función con crecimiento cuasi polinómico , y se dice que los algoritmos con esta complejidad temporal toman un tiempo cuasi polinómico . [2]
Todas las funciones polilogarítmicas de n son o( n ε ) para cada exponente ε > 0 (para conocer el significado de este símbolo, consulte la notación o pequeña ), 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 suave Õ( n ) . [3]
