対数関数的成長

対数関数的成長（たいすうかんすうてきせいちょう、英：logarithmic growth）または対数関数的増加、対数的増加とは、ある量の増大する速さが時間が経つにつれて、どんどん減少する対数関数で表せる現象のことである（例：${\displaystyle y=C\log {x}}$）。対数関数的成長は指数関数的成長の逆であり、増加する速さがとても遅い^[1]。

例えば、位取り記数法で表される正の整数 ${\displaystyle N}$ の桁数の増長は対数関数 ${\displaystyle y=\log _{b}{N}}$ で表せ、桁数は ${\displaystyle y=\lfloor {\log _{b}{N}+1}\rfloor }$ で表せる。ただし、${\displaystyle b}$ がその記数法の基数である。例えば十進法で表した数 ${\displaystyle 10}$ を上式に代入したら ${\displaystyle y=\lfloor {\log _{10}{10}+1}\rfloor =2}$ 、${\displaystyle 100}$ を代入したら ${\displaystyle y=\lfloor {\log _{10}{100}+1}\rfloor =3}$ と成り立っている^[2]。

高等数学では、調和級数の部分和が対数関数的成長の例である^[3]。

${\displaystyle \sum _{n=1}^{k}{\frac {1}{n}}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots +{\frac {1}{k}}}$

アルゴリズム設計において、対数関数的成長とその変体である対数線形などが作業効率を表すことに魅力的である。二分探索などのプログラムの時間複雑度の分析にも用いられている^[4]。

微生物学では、細胞培養における急速に増加する指数関数的増長する段階は、対数関数的増長と呼ばれることがある。この増殖曲線で、現れる新しい細胞が細胞の総数と比例していることがわかるが、この専門用語の混同問題は対数スケールで指数関数的成長の曲線を直線にすることができることで釈明できる^[5]。