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

במתמטיקה, פונקציה פולילוגריתמית ב-$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^{ϵ})$ עבור כל מעריך $ϵ>0$, כלומר, פונקציה פוליגריתמית גדלה לאט יותר מכל פונקציה מעריכית חיובית.

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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