polynomially bounded
\(
f(x)=O(n^k), \forall k\in R
\)
\(
\log(f(x))=O(\log n)
\)
小於
\(
\log n
\)
的為
polynomially bounded.
ptt參考
Log
\( \log \)底數沒寫出來通常是\( 10 \)
\( \lg \)為\( \log \)底數為\( 2 \)
\( \ln \)為\( \log \)底數為\( e \) =
Euler's number
\(
=1+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\dots = 2.718\dots
\)
\(
\lg 3 \approx 1.58
\)
\(
\log n = o(n^{0.1\dots })
\)
\(
1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots +\frac{1}{n}=\Theta(\log n)
\)
\(
\lg(n!)=\Theta(n\log n)
\)
master theorem:
\(
T(n)=aT(\frac{n}{b})+f(n)
\)
\(
(\log_an)^b = o(n^k)
\),
\(
k=\log_{\lg n}(\frac{f(n)}{n^{\log_ba}})
\)