多対数関数

数学では、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のすべての多重対数関数は、すべての指数ε > 0に対してo( n ^ε )となります(この記号の意味については、小文字の o 表記を参照)。つまり、多重対数関数は、任意の正の指数よりもゆっくりと増加します。この観察が、ソフト O 表記Õ( n )の基礎となっています。^{[ 3 ]}