メモ４ - 日記

多分いろいろ間違っているし冗長だと思う。もう少しマニアックなところを補足していきたい。定数 a>1, k>1。階層定理(wikipedia:en:Time_hierarchy_theorem)。L'Hôpital's rule (wikipedia:ja:ロピタルの定理)。

(n に関する) 単調増加関数	備考
A(n)	Ackermann関数。A(n) = A(n, n)。wikipedia:ja:アッカーマン関数
$n\uparrow{^a} n, n\uparrow\uparrow\ldots\uparrow n$	Knuthの矢印表記 (wikipedia:ja:クヌースの矢印表記)？指数タワー関数？
$n\uparrow{^n} k$	.
$n^n$	n!　Stirlingの近似公式。wikipedia:ja:スターリングの近似
$a^n$	指数関数
$n\uparrow{^a} k$	これは結局多項式扱い
$n^k$	多項式 (単項式)
$n\log^k n$	n x polylog(n)
$n\log n$	log n も polylog(n)? 定義忘れた。
$n\log^{1/k}n$	.
$n^1$	線形式
$\frac{n}{\log n}$	$\frac{n}{{\rm polylog}(n)}$
$n^{1/k}$	.
$\log^k n$	$(\log n)^k$
$a^{\sqrt{\log_a n}}$	.
log n	.
$\log^{1/k}n$	$(\log n)^{1/k}$
$\log^{(k)} n$	ex.) $\log^{(5)}n = \log (\log (\log (\log (\log n))))$
log* n	$\log^* n = k \leftrightarrow k = \min_i\{\log^{(i)} n \le 1\}$
α(n)	Ackermann関数の関数的逆？Ackermann逆関数？どっち？n = アボガドロ定数でもα(n) < 5。
1	.