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

במתמטיקה, פונקציה פולילוגריתמית ב-$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 לראשוניות וחיפוש שכן קרוב.$\log ^{k}n$

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

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

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

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