阶的估计 渐近界

hbghlyj

设 $f$ 和 $g$ 是定义域为 $\Bbb N$ 上的函数.

• 若存在正数 $c$ 和 $n_0$，使得对一切 $n ≥ n_0$ 有 $0 ≤ f(n) ≤ c g(n)$ 成立, 则称 $f(n)$ 的渐近的上界是 $g(n)$，记作 $f (n) = O(g(n))$.
• 若存在正数 $c$ 和 $n_0$，使得对一切 $n ≥ n_0$ 有 $0 ≤ cg(n) ≤ f(n)$ 成立, 则称 $f(n)$ 的渐近的下界是 $g(n)$,记作 $f (n) = Ω (g(n))$.
• 若对于任意正数 $c$ 都存在 $n_0$，使得对一切 $n ≥ n_0$ 有 $0 ≤ f(n) < c g(n)$ 成立, 则记作 $f (n) = o(g(n))$.
• 若对于任意正数 $c$ 都存在 $n_0$，使得对一切 $n ≥ n_0$ 有 $0 ≤ cg(n) < f(n)$ 成立, 则记作 $f (n) = ω (g(n))$.
• 若 $f (n) = O (g(n))$ 且 $f (n) = Ω (g(n))$, 则记作$f (n) = Θ (g(n))$

---

(1) 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)$ 存在, 并且等于某个常数 $c>0$, 那么 $f(n)=\Theta(g(n))$.
(2) 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)=0$, 那么 $f(n)=o(g(n))$.
(3) 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)=+\infty$, 那么 $f(n)=\omega(g(n))$.

---

函数的阶之间的关系具有传递性:
• 如果 f=O(g) 且 g=O(h)，那么 f = O(h).
• 如果 f=Ω(g) 且 g=Ω(h)，那么 f = Ω(h).
• 如果 f=Θ(g) 和 g=Θ(h)，那么 f = Θ(h).
定理 假设函数 $f$ 和 $g$ 的定义域为$\Bbb N$，
若对某个其它函数 $h$, 有 $f =O(h)$ 和 $g=O(h)$，
那么 $f + g = O(h)$.
该性质可以推广到有限个函数.

---

多项式函数的阶低于指数函数的阶$n^{d}=o\left(r^{n}\right), \quad r>1, d>0$
对数函数的阶低于幂函数的阶$\ln n=o\left(n^{d}\right),\quad d>0$
换底公式$⇒\log_b(n)=\Theta (\log n)$
积分估计$⇒\log(n!) = \Theta (n\log n)$
Stirling公式$$n !=\sqrt{2 \pi n}\left(\frac{n}{\mathrm{e}}\right)^{n}\left(1+\Theta\left(\frac{1}{n}\right)\right)$$
Mathematica:

1. DiscreteAsymptotic[n!, n -> \[Infinity]]

复制代码

---

渐近展开

1. AsymptoticSolve[E^y - Cos[x y] + x == 0, {y, 0}, {x, 0, 7}]

复制代码

$$y\to -\frac{141 x^7}{56}-\frac{13 x^6}{8}-\frac{6 x^5}{5}-\frac{3 x^4}{4}-\frac{x^3}{3}-\frac{x^2}{2}-x$$

1. AsymptoticSum[1/k, {k, 1, n}, n -> \[Infinity]]

复制代码

\[\sum_{k=1}^n\frac1k\sim\log n\]

1. AsymptoticSum[1/Sqrt[k], {k, 1, n}, {n, \[Infinity], 3}]

复制代码

\[\sum_{k=1}^n\frac1{\sqrt k}\sim-\frac{1}{24 n^{3/2}}+2 \sqrt{n}+\frac{1}{2 \sqrt{n}}+\zeta \left(\frac{1}{2}\right)\]

---

取整函数的性质
(1) $x-1<\lfloor x\rfloor \leq x \leq\lceil x\rceil<x+1$
(2) $\lfloor x+n\rfloor=\lfloor x\rfloor+n,\lceil x+n\rceil=\lceil x\rceil+n$, $n$ 为整数
(3) $\left\lceil\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{2}\right\rfloor=n$
(4) $\left[\frac{\left.\mid \frac{n}{a}\right\rceil}{b}\right]=\left[\frac{n}{a b}\right], \quad\left\lfloor\frac{\left\lfloor\frac{n}{a}\right]}{b}\right]=\left\lfloor\frac{n}{a b}\right\rfloor$

---

递推数列的阶的估计
例子
$$a_n=\sqrt{n}a_{⌊\sqrt{n}⌋}+n$$
Assume $n$ is of the form:
$$n = c^{2^k} \quad \quad k \in \mathbb{N}, c \in \mathbb{N}^+$$
Then the base case will always resolve to a constant $c$.
cs.stackexchange.com: Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$
Mathematica:AsymptoticRSolveValue

1. AsymptoticRSolveValue[{a[n] == Sqrt[n] a[Sqrt[n]] + n, a[7] == 3}, a[n], n -> \[Infinity]]

复制代码

Find a General Asymptotic Approximation (AsymptoticRSolveValue)

hbghlyj

$k$为定值, $\displaystyle {n\choose k}$是$n$的多项式, 可以写成${\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}}$, 所以$\displaystyle{n\choose k}=\Theta(n^k)$
维基百科有很多估计二项式系数的的界的公式

也可以代入Stirling公式计算, 见这篇博客: