Funkcja polilogarytmiczna

Nie mylić z polilogarytmem .

W matematyce funkcja polilogarytmiczna w n jest wielomianem w logarytmie n , _

${\ Displaystyle a_ {k} (\ log n) ^ {k} + a_ {k-1} (\ log n) ^ {k-1} + \ cdots + a_ {1} (\ log n) + a_ { 0}.}$

Notacja log ^k n jest często używana jako skrót dla (log n ) ^k , analogicznie do sin ² θ dla (sin θ ) ² .

W informatyce funkcje polilogarytmiczne występują jako porządek czasu lub pamięci używany przez niektóre algorytmy (np. „ma porządek polilogarytmiczny”) .

Wszystkie funkcje polilogarytmiczne n są o( n ^ε ) dla każdego wykładnika ε > 0 (znaczenie tego symbolu można znaleźć w małej notacji o ), to znaczy funkcja polilogarytmiczna rośnie wolniej niż jakikolwiek wykładnik dodatni. Ta obserwacja jest podstawą miękkiej notacji O Õ( n ) .

• Czarny, Paul E. (2004-12-17). „polilogarytmiczny” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 2010-01-10 .