algorithm - sigla - ¿Cuál es el significado de O(polylog(n))? En particular, ¿cómo se define polylog(n)?
tag significado en español (6)
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: Polylogarítmico , o, para verlo en contexto, el blog del profesor Scott Aaronson: Mis tasas de crecimiento favoritas ).
El punto es que así como a menudo no nos importan 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))" - O con una tilde encima de ella - lo que significa "O (f (n) polylog (f (n)))", es decir , "O (f (n) (log f (n)) k ) para algunos k".
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 función de análisis complejo Li s (Z) , creo. ¿O son? ¿Algo totalmente diferente tal vez?
Mas detalle:
Sobre todo para 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 matrices de sufijos comprimidos . 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 analítica de números. 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 apreciado.
Diferente artículo poligonal . Supongo que es bastante cercano.
Estoy seguro de que solo se refieren al eje real entero positivo: Re(n) = n
La forma en que se usa en este documento parece describir algo como:
O (log ^ pn)
Polylog (n) es solo "polinomio en el registro de n". Wikipedia
Wolfram le da una selección , de la cual la página de polilogaritmos parece más prometedora.