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

במתמטיקה, פונקציה פולילוגריתמית ב- היא פולינום בלוגריתם של , מהצורה: .

למשל, הפונקציה { היא פונקציה פולילוגריתמית.

לפעמים הביטוי  נכתב בצורה , כמו שהביטוי  נכתב לעיתים .

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

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

כל הפונקציות הפולילוגריתמיות הן  עבור כל מעריך , כלומר, פונקציה פוליגריתמית גדלה לאט יותר מכל פונקציה מעריכית חיובית.

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


קטגוריה:פולינומים
קטגוריה:לוגריתמים
קטגוריה:אנליזה מתמטית