OI 中的等价无穷大方程
Published:
定义
\[\lim\limits_{x \to \infty} \frac {A(x)} {B(x)} = 1 \iff A(x) \sim B(x)\]下文中无歧义的情况下，$\lim$ 代表 $\lim\limits_{x \to \infty}$，函数省略 $(x)$。
性质
$A \sim B$ 两边可以同时乘除等价的函数。
$A \sim B$ 两边可以同时求幂。
\[\begin{aligned} & \lim \frac {A'} {B'} \\ =& \lim \frac A B & \text{L'Hôpital's Rule} \\ =& 1 \end{aligned}\]在可以洛的前提下，$A \sim B$ 两边可以同时求导。
\[\begin{aligned} & \lim \frac {\ln A} {\ln B} \\ =& \lim \frac {A'/A} {B'/B} & \text{L'Hôpital's Rule}\\ =& 1 \end{aligned}\]在可以洛的前提下，$A \sim B$ 两边可以同时求对数。
例题
例 1：莫队
\[\begin{aligned} B &\sim \frac n B \\ B^2 &\sim n \\ B &\sim \sqrt n \\ \end{aligned}\]例 2：P2801 教主的魔法
令分块块长为 $B$，则复杂度最优化则是要解以下方程：
\[\begin{aligned} B &\sim \frac {n \ln B} B \\ \frac {B^2} {\ln B} &\sim n \\ 2 \ln B - \ln \ln B &\sim \ln n & \text{两边同时} \ln \\ 2 \ln B &\sim \ln n & \text{忽略低阶无穷大}\\ n \ln B &\sim \frac {n \ln n} 2 \\ B^2 &\sim \frac {n \ln n} 2 & \text{与原式传递} \\ B &\sim \frac {\sqrt 2} 2 \sqrt{n \ln n} \\ \end{aligned}\]