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

Breve:
Cuando los artículos académicos (ciencias de la computación) dicen "O (polylog (n))", ¿qué significan? No estoy confundido por la notación "Big-Oh", con la que estoy muy familiarizado, sino por la función polylog (n). No están hablando de la compleja función de análisis Li_s(Z), creo. ¿O son? ¿Algo totalmente diferente tal vez?¿Cuál es el significado de O (polylog (n))? En particular, ¿cómo se define polylog (n)?

más detalle:
Sobre todo para el interés personal, hace poco he estado buscando durante varios papeles en comprimido sufijo matrices, por ejemplo, Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays. Las estimaciones de complejidad computacional indicadas a veces incluyen 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 análisis complejo y teoría de números analíticos. Mi sospecha es que no está relacionado con el polílogo (n) en los documentos de compresión, aunque me gustaría saber lo contrario de alguien con más conocimiento. Si este es el caso, ¿por qué exactamente se considera razonable omitir el subíndice?

Mi única otra suposición es que quizás O (polylog (n)) se supone que significa "asintótico a una función polinómica de log (n)". Pero eso es solo una suposición: no tengo evidencia de esto, y sería un abuso de notación para arrancar.

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

Fuente

2009-11-26 Managu

¿Dónde lo has visto? –

En el resumen vinculado, se establece "... el CSA se puede buscar en O (m) vez que sea = O (polylog (n))". – Managu

Oh, quizás Sadakane [SODA 2002] tenga su respuesta definitiva. –

Abuso de notación o no, polylog (n) significa "algún polinomio en log (n)", así como "poli (n)" puede significar "algún polinomio en n". Entonces O (polylog (n)) significa "O ((log n) ^k) para algunos k". (Ver Wikipedia: Polylogarithmic, o, para verlo en su contexto, el blog del Prof. Scott Aaronson:. My Favorite Growth Rates)

El punto es que al igual que a menudo no se preocupan por factores constantes, a menudo es conveniente hacer caso omiso de los poderes de los logaritmos . A veces los "factores de registro" se ignoran por completo y es posible que vea "Õ (f (n))" - O con una tilde encima de él - que means "O (f (n) polylog (f (n)))", es decir , "O (f (n) (log f (n)) ^k) para algunos k".

Fuente

2009-11-26 01:55:02 ShreevatsaR

Bastante justo. Gracias por los enlaces! – Managu

'a menudo es conveniente ignorar los poderes de los logaritmos' Extraño. ¿Cómo es posible ignorar los poderes de los logaritmos cuando cambia el significado por completo? – Lazer

@eSKay: de la misma manera, a menudo es conveniente ignorar los factores constantes a pesar de que cambia el significado por completo, solo depende de lo que desee enfocarse. Cualquier función polilogarítmica crece más lenta que O (n^ε) para * every * ε. Entonces, cuando lo que más te importa es el exponente en n - e.g. tratando de distinguir entre n^2.1 y n^2 - estos factores polilográficos no importan. O (n^2 polylog (n)) es O (n^(2 + ε)) para todo ε, por lo que escribimos Õ (n^2). – ShreevatsaR