時間複雜度大小關係(Time Complexity Order)
時間複雜度大小關係(Time Complexity Order)
各sort時間複雜度
Sort 時間複雜度
limit
-
if
\(
\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}=0
\)
\(
\Rightarrow
f(n)=o(g(n))
\)
\(
\rightarrow
f(n)=O(g(n))
\)
-
if
\(
\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}=L>0
\)
\(
\Rightarrow
f(n)=\Theta(g(n))
\)
-
if
\(
\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}=\infty
\)
\(
\Rightarrow
f(n)=\omega(g(n))
\)
\(
\rightarrow
f(n)=\Omega(g(n))
\)
Exercise
log法
\(
\log(f(n))=o(\log(g(n)))
\rightarrow
f(n)=o(g(n))
\)
\(
\log(f(n))=w(\log(g(n)))
\rightarrow
f(n)=w(g(n))
\)
***
\(
\log(f(n))=\theta(\log(g(n)))
\not\rightarrow
f(n)=\theta(g(n))
\)
Integral && Squeeze
src