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

במתמטיקה, פונקציה פולילוגריתמית ב-$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)$).

אלגוריתמים בסיבוכיות פולילוגריתמית הם מבחן AKS לראשוניות וחיפוש שכן קרוב.

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

קישורים חיצוניים

• תבנית:Cite web