פונקציה פולילוגריתמית

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

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

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

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