פונקציה פולילוגריתמית
במתמטיקה, פונקציה פולילוגריתמית ב-$ 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 $ היא פונקציה פולילוגריתמית.
לפעמים הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): (\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.
פונקציה פולילוגריתמית34995470Q3395620