دالة متعددة اللوغاريتمات

في الرياضيات ، ^الدالة متعددة اللوغاريتمات في n هي متعددة الحدود في لوغاريتم n ، [ ^{1 ]}

${\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.}$

غالبًا ما يتم استخدام الترميز log ^k n كاختصار لـ (log n ) ^k ، على غرار sin ² θ لـ (sin θ ) ² .

في علوم الحاسوب ، تُستخدم الدوال متعددة اللوغاريتمات كترتيب زمني لبعض عمليات بنية البيانات . بالإضافة إلى ذلك، تُنتج الدالة الأسية للدالة متعددة اللوغاريتمات دالة ذات نمو شبه متعدد الحدود ، ويُقال إن الخوارزميات التي يكون تعقيدها الزمني هو هذا ، تستغرق وقتًا شبه متعدد الحدود . ^{[ 2 ]}

جميع الدوال متعددة اللوغاريتمات لـ n هي من الرتبة o( nε ⁾ لكل أس ε > 0 (للاطلاع على معنى هذا الرمز، انظر ترميز o الصغير ) ، أي أن الدالة متعددة اللوغاريتمات تنمو ببطء أكبر من أي أس موجب. هذه الملاحظة هي أساس ترميز O الناعم Õ( n ) . ^{[ 3 ]}