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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

במתמטיקה, פונקציה פולילוגריתמית ב-n היא פולינום בלוגריתם של n, מהצורה: ak(logn)k+ak1(logn)k1++a1(logn)+a0.

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

לפעמים הביטוי (logn)k נכתב בצורה logkn, כמו שהביטוי (sinx)2 נכתב לעיתים sin2x.

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

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

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

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

  • בלאק, פול (2004-12-17). "polylogarithmic". מילון אלגוריתמים ומבני נתונים. מכון התקנים והטכנולוגיה האמריקאי. נבדק ב-2010-01-10.
ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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