במתמטיקה, פונקציה פולילוגריתמית ב-${\displaystyle n}$ היא פולינום בלוגריתם של ${\displaystyle n}$, מהצורה: ${\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}}$.

למשל, הפונקציה {${\displaystyle f(x)=5(\log 2)^{4}+11(\log 2)^{3}+5.5(\log 2)^{2}+\log 2+3}$ היא פונקציה פולילוגריתמית.

לפעמים הביטוי ${\displaystyle (\log n)^{k}}$ נכתב בצורה ${\displaystyle \log ^{k}n}$, כמו שהביטוי ${\displaystyle (\sin x)^{2}}$ נכתב לעיתים ${\displaystyle \sin ^{2}x}$.

במדעי המחשב, פונקציות פולילוגריתמיות הן סדר סיבוכיות זמן או מקום של אלגוריתמים מסוימים (למשל, "אלגוריתם בעל סיבוכיות פולילוגריתמית"). סיבוכיות זו גדולה מסיבוכיות לוגריתמית ${\displaystyle O(\log(n))}$, וקטנה מסיבוכיות ליניארית (${\displaystyle O(n)}$).

אלגוריתמים בסיבוכיות פולילוגריתמית הם מבחן AKS לראשוניות וחיפוש שכן קרוב.${\displaystyle \log ^{k}n}$

כל הפונקציות הפולילוגריתמיות הן ${\displaystyle o(n^{\epsilon })}$ עבור כל מעריך ${\displaystyle \epsilon >0}$, כלומר, פונקציה פוליגריתמית גדלה לאט יותר מכל פונקציה מעריכית חיובית.

• בלאק, פול (2004-12-17). "polylogarithmic". מילון אלגוריתמים ומבני נתונים. מכון התקנים והטכנולוגיה האמריקאי. נבדק ב-2010-01-10.

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.