Funció polilogarítmica

En matemàtiques, una funció polilogarítmica^[1] en $n$ és un polinomi format a partir del logaritmo de $n$ , és dir:

a_{k} (\log n)^{k} + a_{k - 1} (\log n)^{k - 1} + \dots + a_{1} (\log n) + a_{0} .

La notació $log Plantilla:Sup n$ s'utilisa a sovint com forma concisa per a $(log n) Plantilla:Sup$ , anàloga a $sense Plantilla:Sup θ$ per a $(sense θ) Plantilla:Sup$ .

En ciències de la computació, les funcions polilogarítmicas es donen com orde de magnitut del temps de càlcul necessari per a algunes operacions d'estructura de senyes. Ademés, la funció exponencial d'una funció polilogarítmica produïx una funció en creiximent casi polinòmic, i es diu que els algoritmes en esta complexitat temporal requerixen temps casi polinòmic.^[2]

Totes les funcions polilogarítmicas de $n$ són $o(n Plantilla:Sup)$ per a cada exponent $ε > 0$ (per al significat d'este símbol, consulte's cota superior asintòtica), és dir, una funció polilogarítmica creix més llentament que qualsevol exponent positiu. Esta observació és la base de la notació O dèbil $Õ(n)$ .^[3]

Referències

↑ Black, Paul E.. «polylogarithmic». Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Consultat el 10 de giner de 2010.
↑ Plantilla:ComplexityZoo
↑ (2022) Introduction to Algorithms, 4th edició, Cambridge, Mass.: The MIT Press, pp. 74–75. ISBN 9780262046305.

Referències

Este artícul conté una traducció derivada de «Función polilogarítmica» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Black, Paul E.. «polylogarithmic». Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Consultat el 10 de giner de 2010.

[2] Plantilla:ComplexityZoo

[3] (2022) Introduction to Algorithms, 4th edició, Cambridge, Mass.: The MIT Press, pp. 74–75. ISBN 9780262046305.

[1]

[2]

[3]