渐进记号

1.渐进记号: Θ

Θ的数学含义 方式一：设f(n)和g(n)是定义域为自然数集合的函数。如果$\begin{align*} & \lim_{n \to \infty} \frac{f(n)}{g(n)}$存在，并且等于某个常数c(c>0)，那么f(n)=Θ(g(n))。通俗理解为f(n)和g(n)同阶，Θ用来表示算法的精确阶。

方式二：Θ(g(n))={f(n):存在正常量c1、c2和n0，使得对所有n≥n0，有0≤c1g(n)≤f(n)≤c2g(n)}若存在正常量c1、c2，使得对于足够大的n，函数f(n)能“夹入”c1g(n)与c2g(n)之间，则f(n)属于集合Θ(g(n))，记作f(n)∈Θ(g(n))。作为代替，我们通常记“f(n)=Θ(g(n))”。

$$\begin{align*} & \lim_{n \to \infty} \frac{f(n)}{g(n)}$$

$\begin{align*} & \lim_{n \to \infty} \frac{f(n)}{g(n)}$

$$\begin{align*} \lim_{n \to \infty} \frac{f(n)}{g(n)}$$