¿Cuál es el significado de O (polylog (n))? En particular, ¿cómo se define polylog (n)?

Question

Breve:
Cuando los documentos académicos (ciencias de la computación) dicen "O (polylog (n))", ¿qué significan? No estoy confundido por el " Big-Oh " Notación, con la que estoy muy familiarizado, pero más bien por la función polylog (n). No están hablando de la compleja función de análisis Li _s (Z) Pienso. ¿O son? ¿Algo totalmente diferente tal vez?

Más detalles:
Sobre todo para el interés personal, recientemente he estado revisando varios artículos sobre matrices de sufijos comprimidos, por ejemplo. Ventajas de la búsqueda hacia atrás: memoria secundaria eficiente e implementación distribuida de arreglos de sufijos comprimidos . Las estimaciones de complejidad computacional indicadas a veces involucran polylog (n), que es una función con la que no estoy familiarizado.

Wikipedia da una definición de polylog _s (z) que Parece ser principalmente sobre el análisis complejo y la teoría numérica analítica. Mi sospecha es que no está relacionado con el polylog (n) en los papeles de compresión, aunque me encantaría escuchar de otra manera a alguien más informado. Si este es el caso, ¿por qué exactamente se considera razonable omitir el subíndice?

Mi única otra suposición es que tal vez O (polylog (n)) se supone que significa "Asintomática a una función polinomial de log (n)". Pero eso es solo una conjetura: no tengo evidencia de esto, y sería un abuso de notación para iniciar.

En cualquier caso, ¡un enlace a una definición razonablemente autorizada sería muy apreciado!

Answer 1

Abuso de notación o no, polylog (n) significa "algún polinomio en log (n)", tal como poly (n) " puede significar " algún polinomio en n " ;. Así que O (polylog (n)) significa "O ((log n) ^k ) para algunos k". (Vea Wikipedia: Polylogarithmic , o, para verlo en contexto, el blog del Prof. Scott Aaronson: < a href = "http://scottaaronson.com/blog/?p=263" rel = "noreferrer"> Mis tasas de crecimiento favoritas .)

El punto es que, como a menudo no nos preocupan los factores constantes, a menudo es conveniente ignorar los poderes de los logaritmos. A veces, los " factores de registro " se ignoran por completo y es posible que vea " Õ (f (n)) " - & nbsp; O con una tilde encima de ella - que significa " O (f ( n) polylog (f (n))), es decir, O (f (n) (log f (n)) ^k ) para algunos k " ;.

Answer 2

La forma en que se usa en este documento Parece estar describiendo algo como:

O (log ^ p n)

Answer 3

Polylog (n) es solo un polinomio en el registro de n " ;. Wikipedia

Answer 4

Diferente artículo de polylog . Supongo que está bastante cerca.

Answer 5

Estoy seguro de que solo significan el eje real positivo entero: Re (n) = n

Answer 6

Wolfram le ofrece una selección , de la que polilogaritmo La página parece más prometedora.